\(5.4\ NOI\)模拟

\(T1\)

想到分讨,但是暴力输出一下方案之后有很多特别的情况要讨论,就弃了…

假设\(a\)是原序列,\(b\)是我们得到的序列

设\(i\)是最长公共前缀,\(j\)是最长公共后缀

我们假设询问的是整个序列,若\(i+j=n-1\)那我们的方案数是\(m-1\),较为显然

否则\(i+j<=n-2\)

首先比较显然的是,由于已知串确定,可以根据最长公共前后缀长度进行分类,即可不重不漏的计算每一种情况

那么\(a[i+1]\)和\(a[n-j]\)至少有一个出现在最长公共序列(可能取出来的公共序列不是同一个)里

我们枚举\(i,j\)

假设\(i+j<=n-2\)

\(Sit_1:a[i+1]\neq a[i+2]\)可以增加\(m-1\)种情况

\(Sit_2:a[n-j]\neq a[n-j-1]\)可以增加\(m-1\)种情况

\(Sit_3:a[i+1]\neq a[i+2]\)且\(a[n-j]\neq a[n-j-1]\)那么就\(a[i+1…n-j-2]=a[i+3…n-j],\)可增加\(1\)种情况

我们的答案是\(Sit_1+Sit_2-Sit_3\)

就是说我们可能出现\(1,2\)重复计算情况减去一部分就好了

那么暴力的话可以枚举\(i,j\)进行计算,可以发现,前两种情况,我们可以合并统计

对于第三种情况,我们只需要找到所有满足条件的\(i,j\)即可

那么枚举\(i\)那么\(j>=n-i-2-lcp(a[i+1..n],a[i+3…n])\)既满足\(a[n-j]\neq a[n-j-1],\)用\(Sit_3\)反证即可

合并的意思是,还是说 颜色块数\(\times n\times (m-1)\) 就好了,就没有那么多的分讨了

\(lcp\)求和的话发现有单调性,可使用双指针,复杂度降到\(O(n)\)

\(T2\)

\(Give\ up\)

教练说必须过,就写了一个下午加一个晚上

#include<bits/stdc++.h>
#define MAXN 18900005
#define MAXM 200005
#define ll long long
using namespace std;
const int mod=998244353,INF=1000000000;
int my_pow(ll a,ll b)
{
    ll res=1;
    while(b)
    {
        if(b&1)
        {
           res=(1ll*res*a)%mod;
        }
        a=(1ll*a*a)%mod;
        b>>=1;
    }
    return res;
}
namespace Seg
{
     int cnt=1;
     queue<int> rub;
     struct node
     {
          int l,r,siz,sum,mul;
     }tr[MAXN];
     int New()
     {
         if(rub.size()==0) return cnt++;
         else
         {
             int id=rub.front();
             rub.pop();
             tr[id].sum=tr[id].siz=tr[id].l=tr[id].r=0;
             tr[id].mul=1;
             return id;
         }
     }
     void Init(int x)
     {
          tr[x].l=tr[x].r=tr[x].siz=tr[x].sum=0;
          tr[x].mul=1;
     }
     void Del(int x)
     {
          if(x==0) return ;
          rub.push(x);
          Del(tr[x].l);
          Del(tr[x].r);
     }
     void push_up(int x)
     {
          ((tr[x].sum=(tr[tr[x].l].sum+tr[tr[x].r].sum)%mod)+=mod)%=mod;
          tr[x].siz=(tr[tr[x].l].siz+tr[tr[x].r].siz);
          ((tr[x].mul=(1ll*tr[tr[x].l].mul*tr[tr[x].r].mul)%mod)+=mod)%=mod;
     }
     void change(int &x,int l,int r,ll poz,ll k)
     {
          x=New();
          tr[x].sum=((k*poz%mod)+mod)%mod;
          tr[x].mul=my_pow(poz,k);
          tr[x].siz=k;
          if(l==r) return ;
          int mid=(l+r)>>1;
          if(poz<=mid) change(tr[x].l,l,mid,poz,k);
          else change(tr[x].r,mid+1,r,poz,k);
     }
     int Merge(int x,int y,int l,int r)
     {
         if(x==0||y==0) return x+y;
         tr[x].sum=(tr[x].sum+tr[y].sum)%mod;
         tr[x].mul=(1ll*tr[x].mul*tr[y].mul)%mod;
         tr[x].siz=tr[x].siz+tr[y].siz;
         if(l==r)
         {
            rub.push(y);
            return x;
         }
         int mid=(l+r)>>1;
         tr[x].l=Merge(tr[x].l,tr[y].l,l,mid);
         tr[x].r=Merge(tr[x].r,tr[y].r,mid+1,r);
         rub.push(y);
         return x;
     }
     void spilt(int x,int l,int r,int k,int &rt1,int &rt2)
     {
          if(x==0)
          {
             rt1=rt2=0;
             return ;
          }
          if(l==r)
          {
             if(k==0) rt1=0,rt2=x;
             else if(k==tr[x].siz) rt1=x,rt2=0;
             else
             {
                 rt1=x;
                 rt2=New();
                 tr[rt2].siz=tr[x].siz-k;
                 tr[rt2].sum=(1ll*l*tr[rt2].siz%mod+mod)%mod;
                 tr[rt2].mul=my_pow(l,tr[rt2].siz);
                 tr[rt1].siz=k;
                 tr[rt1].sum=(1ll*l*tr[rt1].siz%mod+mod)%mod;
                 tr[rt1].mul=my_pow(l,tr[rt1].siz);
             }
             return ;
          }
          int mid=(l+r)>>1;
          if(tr[tr[x].l].siz<=k)
          {
             rt1=x;
             rt2=New();
             spilt(tr[x].r,mid+1,r,k-tr[tr[x].l].siz,tr[rt1].r,tr[rt2].r);
          }
          else
          {
             rt1=New();
             rt2=x;
             spilt(tr[x].l,l,mid,k,tr[rt1].l,tr[rt2].l);
          }
          push_up(rt1); push_up(rt2);
     }
     int Get_Max(int x,int l,int r)
     {
         if(l==r) return l;
         int mid=(l+r)>>1;
         if(tr[tr[x].r].siz) return Get_Max(tr[x].r,mid+1,r);
         return Get_Max(tr[x].l,l,mid);
     }
     int Get_Min(int x,int l,int r)
     {
         if(l==r) return l;
         int mid=(l+r)>>1;
         if(tr[tr[x].l].siz) return Get_Min(tr[x].l,l,mid);
         return Get_Min(tr[x].r,mid+1,r);
     }
}
namespace FHQ
{
      int cnt=1;
      int rt=0;
      vector<int>rub;
      struct node
      {
           int l,r,siz,key,rt[2];;
           bool tag,rtag,ntag;
      }tr[MAXM];
      int New()
      {
          if(rub.size()==0) return cnt++;
          else
          {
              int id=rub.back();
              rub.pop_back();
              tr[id].key=rand();
              tr[id].l=tr[id].r=tr[id].siz=tr[id].rt[0]=tr[id].rt[1]=0;
              tr[id].tag=tr[id].rtag=tr[id].ntag=0;
              return id;
          }
      }
      int New(int x,int k)
      {
          int id;
          if(rub.size()==0) id=cnt++;
          else id=rub.back(),rub.pop_back();
          tr[id].key=rand();
          tr[id].l=tr[id].r=0;
          tr[id].tag=tr[id].rtag=tr[id].ntag=0;
          tr[id].siz=k;
          Seg::change(tr[id].rt[0],-INF,INF,x,k);
          Seg::change(tr[id].rt[1],-INF,INF,-x,k);
          return id;
      }
      void Del(int x)
      {
           if(x==0) return;
           Seg::Del(tr[x].rt[0]);
           Seg::Del(tr[x].rt[1]);
           rub.push_back(x);
           Del(tr[x].l);
           Del(tr[x].r);
      }
      void push_up(int x)
      {
           tr[x].siz=(tr[tr[x].l].siz+tr[tr[x].r].siz+Seg::tr[tr[x].rt[0]].siz);
      }
      void Rev(int x)
      {
           if(x==0) return ;
           tr[x].rtag^=1;
           tr[x].tag^=1;
           swap(tr[x].l,tr[x].r);
      }
      void Neg(int x)
      {
           if(x==0) return ;
           tr[x].ntag^=1;
           tr[x].tag^=1;
           swap(tr[x].rt[0],tr[x].rt[1]);
      }
      void pd(int x)
      {
             if(tr[x].rtag)
             {
                Rev(tr[x].l);
              Rev(tr[x].r);
              tr[x].rtag=0;
           }
           if(tr[x].ntag)
             {
                Neg(tr[x].l);
              Neg(tr[x].r);
              tr[x].ntag=0;
           }
      }
      void spilt(int rt,int k,int &rt1,int &rt2)
      {
           if(rt==0)
           {
              rt1=0; rt2=0;
              return ;
           }
           pd(rt);
           if(tr[tr[rt].l].siz>=k)
           {
              rt2=rt;
              spilt(tr[rt].l,k,rt1,tr[rt2].l);
              push_up(rt2);
           }
           else if(tr[tr[rt].l].siz+Seg::tr[tr[rt].rt[0]].siz<=k)
           {
                rt1=rt;
                spilt(tr[rt].r,k-(tr[tr[rt].l].siz+Seg::tr[tr[rt].rt[0]].siz),tr[rt1].r,rt2);
                push_up(rt1);
           }
           else
           {
               rt1=rt;
               rt2=New();
               tr[rt2].r=tr[rt1].r;
               tr[rt1].r=0;
               k-=tr[tr[rt].l].siz;
               int len=Seg::tr[tr[rt].rt[0]].siz;
               if(tr[rt].tag) swap(tr[rt].rt[0],tr[rt].rt[1]);
               //这里交换的目的是因为大小反过来了,反正是排完序了,我们两个分裂方式不想变
               //那就交换一下
               //最后再交换回来得到,不得不说,这个真的很妙
               Seg::spilt(tr[rt].rt[0],-INF,INF,k,tr[rt1].rt[0],tr[rt2].rt[0]);
               Seg::spilt(tr[rt].rt[1],-INF,INF,len-k,tr[rt2].rt[1],tr[rt1].rt[1]);
               if(tr[rt].tag)
               {
                  swap(tr[rt1].rt[0],tr[rt1].rt[1]);
                  swap(tr[rt2].rt[0],tr[rt2].rt[1]);
                  tr[rt2].tag=1;
               }
               push_up(rt1);
               push_up(rt2);
           }
      }
      int Merge(int rt1,int rt2)
      {
          if(rt1==0||rt2==0) return rt1+rt2;
          pd(rt1); pd(rt2);
          //反正平衡树维护的是区间,合并一下表示排序之后也是无影响的
          if(tr[rt1].key>=tr[rt2].key)
          {
             tr[rt1].r=Merge(tr[rt1].r,rt2);
             push_up(rt1);
             return rt1;
          }
          else
          {
             tr[rt2].l=Merge(rt1,tr[rt2].l);
             push_up(rt2);
             return rt2;
          }
      }
      //感觉很像一个珂朵莉啊
      int Cover(int rt,int l,int r,int k)
      {
          int rt1,rt2,rt3;
          spilt(rt,r,rt1,rt3);
          spilt(rt1,l-1,rt1,rt2);
          Del(rt2);
          rt2=New(k,r-l+1);
          return Merge(Merge(rt1,rt2),rt3);
      }
      int Reverse(int rt,int l,int r)
      {
          int rt1,rt2,rt3;
          spilt(rt,r,rt1,rt3);
          spilt(rt1,l-1,rt1,rt2);
          Rev(rt2);
          return Merge(Merge(rt1,rt2),rt3);
      }
      int Negat(int rt,int l,int r)
      {
          int rt1,rt2,rt3;
          spilt(rt,r,rt1,rt3);
          spilt(rt1,l-1,rt1,rt2);
          Neg(rt2);
          return Merge(Merge(rt1,rt2),rt3);
      }
      int Compress(int x)
      {
          if(x==0) return 0;
          pd(x);
          tr[x].l=Compress(tr[x].l);
          tr[x].r=Compress(tr[x].r);
          tr[x].rt[0]=Seg::Merge(tr[x].rt[0],Seg::Merge(tr[tr[x].l].rt[0],tr[tr[x].r].rt[0],-INF,INF),-INF,INF);
          tr[x].rt[1]=Seg::Merge(tr[x].rt[1],Seg::Merge(tr[tr[x].l].rt[1],tr[tr[x].r].rt[1],-INF,INF),-INF,INF);
          if(tr[x].l) rub.push_back(tr[x].l);
          if(tr[x].r) rub.push_back(tr[x].r);
          return x;
      }
      int Sort(int rt,int l,int r)
      {
          int rt1,rt2,rt3;
          spilt(rt,r,rt1,rt3);
          spilt(rt1,l-1,rt1,rt2);
          rt2=Compress(rt2);
          tr[rt2].l=tr[rt2].r=0;
          tr[rt2].tag=0;
          ll Sum=Seg::tr[tr[rt2].rt[0]].sum;
          ll MAX=Seg::Get_Max(tr[rt2].rt[0],-INF,INF);
          ll MIN=Seg::Get_Min(tr[rt2].rt[0],-INF,INF);
          ll Mul=Seg::tr[tr[rt2].rt[0]].mul;
          printf("%lld %lld %lld %lld \n",(Sum%mod+mod)%mod,(MAX%mod+mod)%mod,(MIN%mod+mod)%mod,(Mul%mod+mod)%mod);
          return Merge(rt1,Merge(rt2,rt3));
      }
}
int n,q,a[MAXN];
signed main()
{
    scanf("%d%d",&n,&q);
    using namespace FHQ;
    Seg::Init(0);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;i++)
    {
        rt=Merge(rt,New(a[i],1));
    }
    for(int i=1,opt,l,r,k;i<=q;i++)
    {
        scanf("%d%d%d",&opt,&l,&r);
        if(opt==1)
        {
           scanf("%d",&k);
           rt=Cover(rt,l,r,k);
        }
        if(opt==2)
        {
           rt=Negat(rt,l,r);
        }
        if(opt==3)
        {
           rt=Reverse(rt,l,r);
        }
        if(opt==4)
        {
           rt=Sort(rt,l,r);
        }
    }
}

\(T3\)

一开始想的是枚举最大值计算有多少种情况,发现在有重复数字时候寄了

错误式子是

\(\large \frac{\sum_{max}max\times C(Num_{min},k-1)}{C(Num,k)}\)

很容易发现一件事,就是我们枚举了最大值可是并不是知道最大值是谁,因为这个是有标号的

那么我们假定同样大小编号大的比较大的话,就能保证不重复了

设\(a\)为降序排序序列,设\(b\)为升序排序序列

我们考虑答案计算

\(\sum_{i=l}^r C(r-i,k-1)\times a[i]\)

这样复杂度不是很优

考场上看到了\(\sum k<=100000,\)感觉\(k\)的种类不是很多,就想着全部预处理出来,没去想根号分治…

考虑进行根号分治

我们要计算区间\((l,r)\)

此时序列降序

我们提前预处理\(dp[i][j]\)表示\(k=i\)时,\(\sum_{z=1}^j C(j-z,k-1)\times b[z],\)也就是\(1-j\)区间选\(k\)个数字最大值的总和

我们现在要求\(\sum_{z=l}^r C(r-z,k-1)\times b[z]=dp[k][r]-\sum_{z=1}^{l-1}C(r-z,k-1)\times b[z]\)

考虑把他转化到\(dp[k][l-1]\)上

\(\sum_{z=1}^{l-1}C(r-z,k-1)\times b[z]=\sum_{j}dp[j][l-1]\times C(r-l+1,k-j)\)

组合意义比较显然,假设我们的贡献在前面,我们可以枚举前面选了多少个,然后后面任选的减去就好了,然后就\(hhh\)了

\(dp[i][j]=dp[i-1][j-1]+dp[i][j-1]\)

把式子拆开

\(\large \sum_{z=1}^j C(j-z,i-1)b[z]=\sum_{z=1}^{j-1} C((j-1)-z,i-2)b[z]+\sum_{z=1}^{j-1} C((j-1)-z,i-1)b[z]\)

较为显然,直接是组合数递推式的样子

#include<bits/stdc++.h>
#define int long long
#define mod 998244353
#define MAXN 100005
#define Lim 300
using namespace std;
int inv[MAXN],fac[MAXN],b[MAXN],a[MAXN],n,q;
int dp[Lim+5][MAXN];
inline int rd(){
    int r = 0 , w = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') w = -1; ch = getchar();}
    while(ch >='0' && ch <='9') {r = r * 10 + ch -'0'; ch = getchar();}
    return r * w;
}
void Init()
{
     inv[0]=fac[0]=1;
     inv[1]=fac[1]=1;
     for(int i=2;i<MAXN;i++)
     {
          fac[i]=(fac[i-1]*i)%mod;
          inv[i]=(mod-mod/i)*inv[mod%i]%mod;
     }
     for(int i=1;i<MAXN;i++)
     {
         inv[i]=(inv[i-1]*inv[i])%mod;
     }
}
int C(int n,int m)
{
    if(m<0||m>n) return 0;
    return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
int my_pow(int a,int b)
{
    int res=1;
    while(b)
    {
          if(b&1)
          {
             res=res*a%mod;
          }
          a=a*a%mod;
          b>>=1;
    }
    return res;
}
signed main()
{
    scanf("%lld%lld",&n,&q);
    Init();
    for(int i=1;i<=n;i++)
    {
        a[i]=rd();
        b[i]=a[i];
    }
    sort(a+1,a+1+n);
    sort(b+1,b+1+n);
    reverse(a+1,a+1+n);
    for(int i=1;i<=n;i++) dp[1][i]=(dp[1][i-1]+a[i])%mod;
    for(int i=2;i<=Lim;i++)
    {
        for(int j=1;j<=n;j++)
        {
            dp[i][j]=(dp[i-1][j-1]+dp[i][j-1])%mod;
        }
    }
//    for(int i=1;i<=n;i++)
//    {
//        cout<<b[i]<<" ";
//    }
//    cout<<"\n";
    for(int i=1,l,r,k;i<=q;i++)
    {
//        cout<<"shu: "<<l<<" "<<r<<"\n";
        l=rd();
        r=rd();
        k=rd();
        l=lower_bound(b+1,b+1+n,l)-b;
        r=upper_bound(b+1,b+1+n,r)-b-1;
//        cout<<"Sit: "<<l<<" "<<r<<"\n";
        printf("%lld ",r-l+1);
        swap(l,r);
        l=n-l+1;
        r=n-r+1;
        int Ans=0;
        if(k==0)
        {
           puts("0");
           continue;
        }
        if(k>r-l+1)
        {
            puts("-1");
            continue;
        }
        if(k>Lim)
        {
            for(int j=l;j<=r;j++)
            {
                Ans=(Ans+C(r-j,k-1)*a[j])%mod;
            }
        }
        else
        {
            Ans=dp[k][r]%mod;
            for(int j=1;j<=k;j++)
            {
                Ans-=C(r-l+1,k-j)*dp[j][l-1]%mod;
            }
            Ans%=mod;
            Ans+=mod;
            Ans%=mod;
        }
        Ans=(Ans*my_pow(C(r-l+1,k),mod-2)%mod);
        printf("%lld\n",Ans);
//        cout<<Ans<<"\n";
    }
    return 0;
}
/*
7 3
83 74 100 89 95 79 72
90 100 3
80 89 1
70 79 2
*/