Codeforces Round #365 (Div. 2) D. Mishka and Interesting sum (离线树状数组+前缀xor)-白红宇

Codeforces Round #365 (Div. 2) D. Mishka and Interesting sum (离线树状数组+前缀xor)

阅读量：5354 次

发布时间：2019-06-15

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

题目链接：

给你n个数，m次查询，每次查询问你l到r之间出现偶数次的数字xor和是多少。

我们可以先预处理前缀和Xor[i]，表示1~i的xor和。因为num^num=0，所以Xor[r] ^ Xor[l - 1]求的是l~r之间出现奇数次的数字xor和。

那怎么求偶数次的呢，那我们可以先求l到r之间不重复出现数字的xor（比如1 1 2 求的是1 ^ 2），然后再xor以上求出的Xor[r] ^ Xor[l - 1]，奇奇消掉就得出答案了。

那求不重复的话，我们用树状数组来处理。先把询问按照r从小到大排序，以便后面的离线处理。map存的是a[i]数字最近出现的位置i，然后用树状数组i位置插入a[i]并且消掉a[i]之前出现的位置i'，这样保证查询不重复xor和最优。

具体看代码，应该能看懂。

1 //#pragma comment(linker, "/STACK:102400000, 102400000") 2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 #include 
           
             8 #include 
            
              9 #include 
             
              10 #include 
              
               11 #include 
               
                12 #include 
                13 using namespace std;14 typedef long long LL;15 typedef pair 
                 
                   P;16 const int N = 1e6 + 5;17 int bit[N], Xor[N], a[N], ans[N], n;18 map 
                  
                    mp; //a[i]最近出现的位置19 struct Query {20 int l, r, id;21 bool operator <(const Query& cmp) const {22 return r < cmp.r;23 }24 }q[N];25 26 void update(int i, int val) {27 for(; i <= n; i += (i&-i))28 bit[i] ^= val;29 }30 31 int sum(int i) {32 int s = 0;33 for(; i >= 1; i -= (i&-i))34 s ^= bit[i];35 return s;36 }37 38 int main()39 {40 int m;41 scanf("%d", &n);42 for(int i = 1; i <= n; ++i) {43 scanf("%d", a + i);44 Xor[i] = Xor[i - 1] ^ a[i]; //前缀xor45 }46 scanf("%d", &m);47 for(int i = 1; i <= m; ++i) {48 scanf("%d %d", &q[i].l, &q[i].r);49 q[i].id = i;50 }51 sort(q + 1, q + m + 1);52 int j = 1; //询问的结构体下标53 for(int i = 1; i <= n; ++i) {54 int &temp = mp[a[i]]; //引用55 if(temp) { //要是不是第一次出现，那就消掉a[i]之前出现的位置56 update(temp, a[i]);57 }58 temp = i;59 update(temp, a[i]); //插入最近的位置60 while(j <= m && i == q[j].r) {61 int l = q[j].l - 1, r = q[j].r;62 ans[q[j].id] = sum(r) ^ sum(l) ^ Xor[r] ^ Xor[l];63 ++j;64 }65 }66 for(int i = 1; i <= m; ++i) {67 printf("%d\n", ans[i]);68 }69 return 0;70 }

View Code

上面是正确的代码，下面是TLE的。

之前用莫队写的，数据小一点应该可以过。

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
            7 using namespace std; 8 const int MAXN = 1e6 + 5; 9 typedef __int64 LL;10 int a[MAXN] , u, ans[MAXN];11 struct que {12 int l , r , id;13 }q[MAXN];14 map 
            
              mp;15 16 bool cmp(que x , que y) {17 if(x.l / u == y.l / u) 18 return x.r < y.r;19 return x.l / u < y.l / u;20 }21 22 int main()23 {24 int n , m;25 while(~scanf("%d" , &n)) {26 for(int i = 1 ; i <= n ; i++) {27 scanf("%d" , a + i);28 }29 scanf("%d", &m);30 for(int i = 1 ; i <= m ; i++) {31 scanf("%d %d" , &q[i].l , &q[i].r);32 q[i].id = i;33 }34 u = (int)sqrt(n*1.0);35 sort(q + 1 , q + m + 1 , cmp);36 int L = 1 , R = 0 , num;37 int temp = 0;38 for(int i = 1 ; i <= m ; i++) {39 while(R > q[i].r) {40 num = --mp[a[R]];41 if(num) {42 temp ^= a[R];43 }44 R--;45 }46 while(R < q[i].r) {47 R++;48 num = ++mp[a[R]];49 if(num > 1) {50 temp ^= a[R];51 }52 }53 while(L < q[i].l) {54 num = --mp[a[L]];55 if(num) {56 temp ^= a[L];57 }58 L++;59 }60 while(L > q[i].l) { //前面的还没算61 L--;62 num = ++mp[a[L]];63 if(num > 1) {64 temp ^= a[L];65 }66 }67 ans[q[i].id] = temp;68 }69 for(int i = 1 ; i <= m ; i++) {70 printf("%d\n", ans[i]);71 }72 }73 return 0;74 }

View Code

转载于:https://www.cnblogs.com/Recoder/p/5741394.html

你可能感兴趣的文章