P4462 异或序列莫队 + 异或技巧-白红宇的个人博客

发布日期：2021-09-25 23:58:05 浏览次数：8 分类：技术文章

本文共 1581 字，大约阅读时间需要 5 分钟。

题意：给定一个k，一段序列。有m个询问，每次给定 [ l , r ] ，询问该区间内，有多少子序列满足异或和等于k。

以下数组 x 为当前点的 value， a 为 x 的前缀异或和。

看到区间异或和，不由的想到可以转换成前缀异或：a( l ) ^ a( l + 1 ) ^ … ^ a( r ) == a( l - 1 ) ^ a( r ) ，现在问题转换成了在 [ l , r ] 内是否存在两个数异或等于k。也就是 a [ x ] ^ a [ y ] = k 。让后看到了这个式子之后还是有点不可做，比如当前区间是 [ l , r ] ，要加上 x [ r + 1 ] 这个数，怎么找另外一个 [ l , r ] 内的数与它异或为 k 的 a [ x ] 呢？显然可以将两边异或a [ r + 1 ]，通过 a [ x ] = a [ r + 1 ] ^ k 得到。剩下的就比较简单了，用一个桶记录一下异或值的个数，直接操作即可。

~~闲的没事加了一些优化，不加也能过。~~

#pragma GCC optimize(2)#include
   
    #include
    
     #include
     
      #include
      
       #include
       #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #define X first#define Y second#define L (u<<1)#define R (u<<1|1)#define Mid (tr[u].l+tr[u].r>>1)#define Len(u) (tr[u].r-tr[u].l+1)#define pb push_back#define mk make_pair#define il inlineusing namespace std;typedef long long LL;typedef pair
               
                 PII;const int N=1000010,mod=1e9+7,INF=0x3f3f3f3f;const double eps=1e-6;int n,m,k;int cnt[N],id[N],a[N],ans[N],res;int now;struct Node{ int l,r; int id;}q[N];template 
                
                 bool read(T &ret)//输入{ char c; int sgn; T bit=0.1; if(c=getchar(), c==EOF) return 0; while(c!='-' && c!='.' && (c<'0' || c>'9')) c=getchar(); sgn=(c=='-')? -1:1; ret=(c=='-')? 0:(c-'0'); while(c=getchar(), c>='0' && c<='9') ret=ret*10+(c-'0'); if(c==' ' || c=='\n') { ret*=sgn; return 1; } while(c=getchar(), c>='0' && c<='9') ret+=(c-'0')*bit, bit/=10; ret*=sgn; return 1;}inline void out(int x)//输出{ if(x>9) out(x/10); putchar(x%10+'0');}bool cmp(Node a,Node b){ return id[a.l]^id[b.l]? id[a.l]
                 
                  b.r : a.r
                  
                   lx) add(--l); while(r>rx) del(r--); while(r

转载地址：https://blog.csdn.net/DaNIelLAk/article/details/108342371 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：P3709 大爷的字符串题莫队离线求众数

下一篇：Count on a tree 树上主席树

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章