傳送門
文章目錄
題意：
給你一個(gè)長度為nnn的序列aaa，讓你計(jì)算
n≤4e5,a≤1e7n\le 4e5,a\le 1e7n≤4e5,a≤1e7
思路：
首先這個(gè)式子是n2n^2n2的，顯然不能直接算，并且異或沒有分配律，所以碰到這種情況我們自然的就想到按位考慮。
分開考慮每一位，假設(shè)當(dāng)前為第kkk位，當(dāng)這一位是111的時(shí)候，兩個(gè)數(shù)的和一定在[2k,2k+1?1][2^k,2^{k+1}-1][2k,2k+1?1]之間，由于有可能會(huì)溢出，比如全是111的情況相加，所以還有可能在[2k+2k+1,2k+2?2][2^k+2^{k+1},2^{k+2}-2][2k+2k+1,2k+2?2]之間，我們可以取出來每個(gè)數(shù)模上2k+12^{k+1}2k+1之后的數(shù)，將他們排個(gè)序，之后雙指針掃一遍，注意要倒著掃才能保證正確性，算一下有多少對在這一位有貢獻(xiàn)的，讓后看奇偶性就好啦。
直接做的復(fù)雜度顯然是nlognloganlognloganlognloga，這個(gè)題顯然是能過去的，但是我們可以再優(yōu)化一下它。
考慮到枚舉每一位是不能優(yōu)化掉的，我們對排序進(jìn)行優(yōu)化。
觀察可以知道我們每次都只考慮某一位之前的數(shù)，并且每次都增加一位，所以我們每次只執(zhí)行一次快排，因?yàn)閷τ谛略黾拥囊晃晃覀兡軐⑵浞殖蓛刹糠?#xff0c;這一位如果是111就放在右邊，否則放在左邊，讓后雙指針掃一下就可以排出序來了。
復(fù)雜度nloganloganloga。
#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<map>
#include<cmath>
#include<cctype>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
#include<sstream>
#include<ctime>
#include<cstdlib>
#define X first
#define Y second
#define pb push_back
#define mk make_pair
#define Mid (tr[u].l+tr[u].r>>1)
#define Len(u) (tr[u].r-tr[u].l+1)
#define random(a,b) ((a)+rand()%((b)-(a)+1))
#define db puts("---")
using namespace std
;
typedef long long LL
;
typedef unsigned long long ULL
;
typedef pair
<int,int> PII
;const int N
=1000010,mod
=1e9+7,INF
=0x3f3f3f3f;
const double eps
=1e-6;int n
;
int a
[N
],b
[N
];
int ans
=0;
int L
[N
],R
[N
],Lid
[N
],Rid
[N
],id
[N
];int get(int L
,int R
) {if(L
>R
) return 0;int ans
=0;for(int i
=n
,l
=1,r
=1;i
>=1;i
--) {while(l
<=n
&&b
[l
]+b
[i
]<L
) l
++;while(r
<=n
&&b
[r
]+b
[i
]<=R
) r
++;ans
+=r
-l
-(l
<=i
&&i
<r
);}return ans
>>1&1;
}void merge(int k
) {int l
,r
; l
=r
=0;for(int i
=1;i
<=n
;i
++) {if(a
[id
[i
]]>>k
&1) R
[++r
]=b
[i
]|(1<<k
),Rid
[r
]=id
[i
];else L
[++l
]=b
[i
],Lid
[l
]=id
[i
];}int p1
=1,p2
=1,p
=1;while(p1
<=l
&&p2
<=r
) {if(L
[p1
]<=R
[p2
]) b
[p
]=L
[p1
],id
[p
++]=Lid
[p1
++];else b
[p
]=R
[p2
],id
[p
++]=Rid
[p2
++];}while(p1
<=l
) b
[p
]=L
[p1
],id
[p
++]=Lid
[p1
++];while(p2
<=r
) b
[p
]=R
[p2
],id
[p
++]=Rid
[p2
++];
}int calc(int x
) {merge(x
);return (get(1<<x
,(1<<(x
+1))-1)+get(3<<x
,(1<<(x
+2))-2))%2;
}int main()
{
scanf("%d",&n
);for(int i
=1;i
<=n
;i
++) scanf("%d",&a
[i
]),id
[i
]=i
;for(int i
=0;i
<25;i
++) ans
+=calc(i
)<<i
;printf("%d\n",ans
);return 0;
}
總結(jié)
以上是生活随笔為你收集整理的Codeforces Round #626 (Div. 2) D. Present 按位贡献 + 快排新姿势的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。
