P4887 第十四分块(前体)（你懂个锤子莫队）

题目链接

• 一般的莫队我们可以

  

  或者

  

  做到相邻转移。使得我们可以接受把一段连续转移拆成根号次相邻转移。
• 那么当我们转移花费高到我们无法接受根号级别的拆分的时候我们怎么办呢。
• 思想是：把L转移到qry.l和R转移到qry.r的部分也离线掉。
• 考场出了大概并做不出来吧，我为什么要花时间研究这个呢。。。
• 摆在这里当个板子吧。。。也许板子也当不了。。。
• 并没有意义的一篇博文

• #include<bits/stdc++.h>
  
  #define qcin; ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  #define pb push_back
  #define clr(x) memset(x,0,sizeof x)
  #define fmax(x) memset(x,0x3f,sizeof x)
  #define finit(x) memset(x,-1,sizeof x)
  
  #define dis(l,r) r-l+1
  #define gstr(str) scanf("%s",str)
  #define glen(str) strlen(str)
  using namespace std;
  
  typedef long long ll;
  
  typedef pair<ll,ll>pll;
  const int maxn = 4e5+10;
  
  int n,m,k,a[maxn],v[maxn],cnt=0,block;
  
  ll sum1[maxn],sum2[maxn],num[maxn],ans[maxn],val[maxn];
  
  struct node{
      int l,r,id;
      void input(int _id){
          scanf("%d%d",&l,&r);
          id=_id;
      }
  }qry[maxn];
  
  vector<node>tmp[maxn];
  
  int cmp(node x,node y){
      return x.l/block==y.l/block?(x.r<y.r):(x.l<y.l);
  }
  
  int main(){
      scanf("%d%d%d",&n,&m,&k);
      for(int i=1;i<=n;i++){
          scanf("%d",&a[i]);
      }
  
      block=sqrt(n);cnt=0;
      for(int i=1;i<=m;i++)qry[i].input(i);
      sort(qry+1,qry+1+m,cmp);
  
      for(int i=0;i<16384;i++){
          if(__builtin_popcount(i)==k)v[cnt++]=i;
      }
      for(int i=1,l=qry[i].r+1,r=l-1;i<=m;i++){
          node now=qry[i];
          if(l<now.l){
              tmp[r].pb(node{l,now.l-1,now.id<<1});
          }else if(now.l<l){
              tmp[r].pb(node{now.l,l-1,now.id<<1});
          }
          l=now.l;
          if(r<now.r){
              tmp[l-1].pb(node{r+1,now.r,now.id<<1|1});
          }else if(now.r<r){
              tmp[l-1].pb(node{now.r+1,r,now.id<<1|1});
          }
          r=now.r;
      }
      
      for(int i=1;i<=n;i++){
          sum1[i]=sum1[i-1]+val[a[i]];
          for(int j=0;j<cnt;j++)
              val[a[i]^v[j]]++;
          sum2[i]=sum2[i-1]+val[a[i]];
          int sz=tmp[i].size();
          for(int j=0;j<sz;j++){
              int l=tmp[i][j].l;
              int r=tmp[i][j].r;
              int id=tmp[i][j].id;
              for(int ni=l;ni<=r;ni++){
                  num[id]+=val[a[ni]];
              }
          }
      }
      ll res=0,w=0;
      for(int i=1,l=qry[i].r+1,r=l-1;i<=m;i++){
          node now=qry[i];
          int L=min(l-1,now.l-1),R=max(l-1,now.l-1);
          w=num[now.id<<1]-(sum2[R]-sum2[L]);
          if(l<now.l)w*=-1;
          res+=w;l=now.l;
          L=min(r,now.r),R=max(r,now.r);
          w=(sum1[R]-sum1[L])-num[now.id<<1|1];
          if(r>now.r)w*=-1;
          res+=w;r=now.r;
          ans[now.id]=res;
      }
      for(int i=1;i<=m;i++){
          printf("%lld\n",ans[i]);
      }
      return 0;
  }