【做題記錄】2025刷題計劃--根號算法
A. Tree Master
考慮根號分治，暴力處理。對于一層，設點數為 \(cnt\)。
- 若 \(cnt>\sqrt{n}\)，這樣的層最多有 \(\sqrt{n}\) 層，每一層最多計算 \(q\) 次，時間復雜度為 \(O(q\sqrt{n})\)。
- 否則 \(cnt\le\sqrt{n}\)，進行記憶化，每一層最多計算 \(cnt\choose 2\) 次，最多有 \(\frac{n}{cnt}\) 層，時間復雜度就是 \(O(n\sqrt{n})\) 的。
于是可以通過。空間復雜度 \(O(n\sqrt{n})\)。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define pb push_back
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=1e5+5;
int n,m,fa[maxn],cnt[maxn];
int dep[maxn],bfn[maxn],blen;
ll a[maxn],**mem[maxn];
vector<int> e[maxn],cun[maxn];
queue<int> q;
il ll dfs(int u,int v){
if(!u&&!v){
return 0;
}
if(cnt[dep[u]]<=blen&&~mem[dep[u]][bfn[u]][bfn[v]]){
return mem[dep[u]][bfn[u]][bfn[v]];
}
ll res=a[u]*a[v]+dfs(fa[u],fa[v]);
if(cnt[dep[u]]<=blen){
mem[dep[u]][bfn[u]][bfn[v]]=mem[dep[u]][bfn[v]][bfn[u]]=res;
}
return res;
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=2;i<=n;i++){
cin>>fa[i];
e[fa[i]].pb(i);
}
blen=sqrt(n);
q.push(1);
while(q.size()){
int u=q.front();
q.pop();
dep[u]=dep[fa[u]]+1;
bfn[u]=cnt[dep[u]];
cun[dep[u]].pb(u);
cnt[dep[u]]++;
for(int v:e[u]){
q.push(v);
}
}
for(int i=1;i<=n;i++){
if(cnt[i]<=blen){
mem[i]=new ll*[cnt[i]]();
for(int j=0;j<cnt[i];j++){
mem[i][j]=new ll[cnt[i]]();
for(int k=0;k<cnt[i];k++){
mem[i][j][k]=-1;
}
}
}
}
while(m--){
int u,v;
cin>>u>>v;
cout<<dfs(u,v)<<"\n";
}
for(int i=1;i<=n;i++){
if(cnt[i]<=blen){
for(int j=0;j<cnt[i];j++){
delete[] mem[i][j];
}
delete[] mem[i];
}
}
return 0;
}
}
int main(){return asbt::main();}
B. [COTS/CETS 2024] 雙雙決斗 Dvoboj
考慮如果沒有修改，用 ST 表就非常舒服。
考慮暴力修改，需要修改所有覆蓋了這個位置的區間，時間復雜度是 \(O(n)\) 的。
而如果只修改 \(\frac{\log n}{2}\) 層，時間復雜度就是 \(O(\sqrt{n})\) 的。查詢時從上往下查，最多查到第 \(\frac{\log n}{2}\) 層，時間復雜度就也是 \(O(\sqrt{n})\) 的。于是就可以通過。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=2e5+5;
int n,m,blen,st[maxn][20];
il int Log(int x){
if(x==1){
return 0;
}
return Log(x>>1)+1;
}
il void upd(int l,int k){
if(k==blen){
return ;
}
if(l-(1<<k)>0){
st[l-(1<<k)][k+1]=abs(st[l-(1<<k)][k]-st[l][k]);
upd(l-(1<<k),k+1);
}
if(l+(1<<(k+1))-1<=n){
st[l][k+1]=abs(st[l][k]-st[l+(1<<k)][k]);
upd(l,k+1);
}
}
il int query(int l,int k){
if(k<=blen){
return st[l][k];
}
return abs(query(l,k-1)-query(l+(1<<(k-1)),k-1));
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>st[i][0];
}
blen=Log(n)>>1;
for(int j=1;j<=blen;j++){
for(int i=1;i+(1<<j)-1<=n;i++){
st[i][j]=abs(st[i][j-1]-st[i+(1<<(j-1))][j-1]);
}
}
while(m--){
int opt,l,k;
cin>>opt>>l>>k;
if(opt==1){
st[l][0]=k;
upd(l,0);
}
else{
cout<<query(l,k)<<"\n";
}
}
return 0;
}
}
int main(){return asbt::main();}
C. 「SMOI-R1」Apple
考慮沒有修改，高維前綴和就很舒服。如果修改就需要同時修改所有超集，時間復雜度是 \(O(2^n)\) 的。
考慮將一個二進制數拆成前后兩段，修改時上傳一段，查詢時下查另一段，時間復雜度就是 \(O(q2^{\frac{n}{2}})\) 的。
Code
#include<bits/stdc++.h>
#define int long long
#define il inline
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
namespace IO{
const int bufsz=1<<20;
char ibuf[bufsz],*p1=ibuf,*p2=ibuf;
#define getchar() (p1==p2&&(p2=(p1=ibuf)+fread(ibuf,1,bufsz,stdin),p1==p2)?EOF:*p1++)
il int read(){
char ch=getchar();
while(ch<'0'||ch>'9'){
ch=getchar();
}
int x=0;
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x;
}
#undef getchar
char obuf[bufsz],*p3=obuf,s[50];
#define flush() (fwrite(obuf,1,p3-obuf,stdout),p3=obuf)
#define putchar(ch) (p3==obuf+bufsz&&flush(),*p3++=(ch))
il void write(int x,bool typ=1){
int top=0;
do{
s[++top]=x%10|48;
x/=10;
}while(x);
while(top){
putchar(s[top--]);
}
putchar(typ?'\n':' ');
}
#undef putchar
class Flush{
public:
~Flush(){
flush();
}
}FL;
#undef flush
}
using IO::read;
using IO::write;
const int maxn=(1<<10)+5,maxm=(1<<20)+5;
int n,m,blen,bsan,b[maxm];
int qan[maxm],hou[maxm];
int a[maxn][maxn];
il void upd(int p,int v){
for(int i=hou[p];;i=(i+1)|hou[p]){
a[qan[p]][i]+=v;
if(i==bsan){
return ;
}
}
}
il int query(int p){
int res=0;
for(int i=qan[p];;i=(i-1)&qan[p]){
res+=a[i][hou[p]];
if(!i){
return res;
}
}
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m;
blen=n>>1;
bsan=(1<<blen)-1;
for(int i=0;i<1<<n;i++){
cin>>b[i];
qan[i]=i>>blen;
hou[i]=i&bsan;
upd(i,b[i]);
}
while(m--){
int opt,p;
cin>>opt>>p;
if(opt==1){
cout<<query(p)<<"\n";
}
else{
int v;
cin>>v;
upd(p,v-b[p]);
b[p]=v;
}
}
return 0;
}
}
signed main(){return asbt::main();}
/*
3 5
0 1 2 3 4 5 6 7
2 1 2
2 2 3
2 3 4
2 6 10
1 7
*/
D. Till I Collapse
考慮當確定了 \(k\) 時，可以 \(O(n)\) 貪心去掃。
顯然 \(k\) 遞增時答案是不增的，同時答案小于 \(\frac{n}{k}\)，所以不同的答案只有 \(O(\sqrt{n})\) 種。
于是對于 \(k<\sqrt{n}\) 暴力掃，對于 \(k\ge\sqrt{n}\) 暴力掃后二分有哪些 \(k\) 的答案是當前這個值。時間復雜度 \(O(n\sqrt{n}\log{n})\)。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=1e5+5;
int n,a[maxn],blen,buc[maxn];
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
// ios::sync_with_stdio(0),cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
blen=sqrt(n);
for(int i=1,ans;i<=blen;i++){
ans=1;
for(int j=1;j<=n;j++){
buc[j]=0;
}
for(int j=1,p=1,num=0;j<=n;j++){
if(buc[a[j]]++==0){
num++;
}
if(num>i){
ans++;
for(int k=p;k<j;k++){
buc[a[k]]--;
}
num=1,p=j;
}
}
cout<<ans<<" ";
}
// puts("666");
for(int i=blen+1,ans,l,r;i<=n;i++){
// cout<<i<<"\n";
ans=1;
for(int j=1;j<=n;j++){
buc[j]=0;
}
for(int j=1,p=1,num=0;j<=n;j++){
if(buc[a[j]]++==0){
num++;
}
if(num>i){
ans++;
for(int k=p;k<j;k++){
buc[a[k]]--;
}
num=1,p=j;
}
}
// cout<<i<<" "<<ans<<"\n";
l=i,r=n;
while(l<r){
int mid=(l+r+1)>>1,res=1;
for(int j=1;j<=n;j++){
buc[j]=0;
}
for(int j=1,p=1,num=0;j<=n;j++){
if(buc[a[j]]++==0){
num++;
}
if(num>mid){
res++;
for(int k=p;k<j;k++){
buc[a[k]]--;
}
num=1,p=j;
}
}
if(res==ans){
l=mid;
}
else{
r=mid-1;
}
}
// cout<<i<<" "<<l<<"\n";
for(int j=i;j<=l;j++){
cout<<ans<<" ";
}
i=l;
}
return 0;
}
}
int main(){return asbt::main();}
E. Mr
根號分治，對于包含的邊數 \(\le\sqrt{m}\) 的顏色暴力枚舉所有點對存入 map，對于大于 \(\sqrt{m}\) 的顏色暴力掃所有查詢。時間復雜度 \(O(m\sqrt{m}\log{m})\)。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define pii pair<int,int>
#define mp make_pair
#define fir first
#define sec second
#define pb push_back
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
namespace IO{
const int bufsz=1<<20;
char ibuf[bufsz],*p1=ibuf,*p2=ibuf;
#define getchar() (p1==p2&&(p2=(p1=ibuf)+fread(ibuf,1,bufsz,stdin),p1==p2)?EOF:*p1++)
il int read(){
char ch=getchar();
while(ch<'0'||ch>'9'){
ch=getchar();
}
int x=0;
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x;
}
#undef getchar
char obuf[bufsz],*p3=obuf,s[50];
#define flush() (fwrite(obuf,1,p3-obuf,stdout),p3=obuf)
#define putchar(ch) (p3==obuf+bufsz&&flush(),*p3++=(ch))
il void write(int x){
int top=0;
do{
s[++top]=x%10|48;
x/=10;
}while(x);
while(top){
putchar(s[top--]);
}
putchar('\n');
}
#undef putchar
class Flush{
public:
~Flush(){
flush();
}
}FL;
#undef flush
}
using IO::read;
using IO::write;
const int maxn=1e5+5;
int n,m,q,blen,ans[maxn];
int fa[maxn],sz[maxn],cun[maxn<<1];
pii wt[maxn];
vector<pii> e[maxn];
map<pii,int> wth;
il int find(int x){
return x!=fa[x]?fa[x]=find(fa[x]):x;
}
il void merge(int u,int v){
u=find(u),v=find(v);
if(u==v){
return ;
}
if(sz[u]<sz[v]){
swap(u,v);
}
sz[u]+=sz[v],fa[v]=u;
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
n=read(),m=read();
// puts("666");
blen=sqrt(m);
for(int i=1,u,v,w;i<=m;i++){
u=read(),v=read(),w=read();
e[w].pb(mp(u,v));
}
// puts("666");
q=read();
for(int i=1,u,v;i<=q;i++){
u=read(),v=read();
if(u>v){
swap(u,v);
}
wt[i]=mp(u,v);
}
for(int i=1;i<=n;i++){
fa[i]=i,sz[i]=1;
}
for(int i=1,tot;i<=m;i++){
if(!e[i].size()){
continue;
}
tot=0;
for(pii j:e[i]){
merge(j.fir,j.sec);
cun[++tot]=j.fir;
cun[++tot]=j.sec;
}
sort(cun+1,cun+tot+1);
tot=unique(cun+1,cun+tot+1)-cun-1;
if(e[i].size()>blen){
for(int j=1;j<=q;j++){
if(find(wt[j].fir)==find(wt[j].sec)){
ans[j]++;
}
}
}
else{
for(int j=1;j<=tot;j++){
for(int k=j+1;k<=tot;k++){
if(find(cun[j])==find(cun[k])){
wth[mp(cun[j],cun[k])]++;
}
}
}
}
for(int j=1;j<=tot;j++){
fa[cun[j]]=cun[j];
sz[cun[j]]=1;
}
}
// puts("666");
for(int i=1;i<=q;i++){
write(ans[i]+wth[mp(wt[i].fir,wt[i].sec)]);
}
return 0;
}
}
int main(){return asbt::main();}
F. ycz的妹子
用線段樹維護區間顏值和與妹子個數即可。時間復雜度 \(O(m\log{n})\)。
Code
#include<bits/stdc++.h>
#define int long long
#define il inline
#define lid id<<1
#define rid id<<1|1
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=5e5+5;
int n,m,a[maxn];
int sum[maxn<<2],sz[maxn<<2];
il void pushup(int id){
sum[id]=sum[lid]+sum[rid];
sz[id]=sz[lid]+sz[rid];
}
il void build(int id,int l,int r){
if(l==r){
if(l<=n){
sum[id]=a[l],sz[id]=1;
}
return ;
}
int mid=(l+r)>>1;
build(lid,l,mid);
build(rid,mid+1,r);
pushup(id);
}
il void upd1(int id,int l,int r,int p,int v){
if(l==r){
sum[id]-=v;
return ;
}
int mid=(l+r)>>1;
if(p<=mid){
upd1(lid,l,mid,p,v);
}
else{
upd1(rid,mid+1,r,p,v);
}
pushup(id);
}
il void upd2(int id,int l,int r,int p,int v){
if(l==r){
sum[id]=v,sz[id]=1;
return ;
}
int mid=(l+r)>>1;
if(p<=mid){
upd2(lid,l,mid,p,v);
}
else{
upd2(rid,mid+1,r,p,v);
}
pushup(id);
}
il void upd3(int id,int l,int r,int p){
if(l==r){
sum[id]=sz[id]=0;
return ;
}
int mid=(l+r)>>1;
if(sz[lid]>=p){
upd3(lid,l,mid,p);
}
else{
upd3(rid,mid+1,r,p-sz[lid]);
}
pushup(id);
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
build(1,1,5e5);
while(m--){
char opt;
cin>>opt;
switch(opt){
case 'C':{
int p,v;
cin>>p>>v;
upd1(1,1,5e5,p,v);
break;
}
case 'I':{
int p,v;
cin>>p>>v;
upd2(1,1,5e5,p,v);
break;
}
case 'D':{
int p;
cin>>p;
upd3(1,1,5e5,p);
break;
}
default:{
cout<<sum[1]<<"\n";
break;
}
}
}
return 0;
}
}
signed main(){return asbt::main();}
G. Robin Hood Archery
考慮兩個人的最優策略，一定都是先射擊分高的。因此后手不可能贏，要求不輸只能 \([l,r]\) 內每個分數都出現偶數次，才能平局。異或哈希即可。時間復雜度 \(O(n)\)。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define ull unsigned ll
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=1e6+5;
int T,n,m,a[maxn];
ull ha1[maxn],ha2[maxn];
ull hs1[maxn],hs2[maxn];
mt19937_64 rdsd(time(0));
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
for(int i=1;i<=1e6;i++){
while(!ha1[i]){
ha1[i]=rdsd();
}
while(!ha2[i]){
ha2[i]=rdsd();
}
}
cin>>T;
while(T--){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
hs1[i]=hs1[i-1]^ha1[a[i]];
hs2[i]=hs2[i-1]^ha2[a[i]];
}
while(m--){
int l,r;
cin>>l>>r;
puts(hs1[r]==hs1[l-1]&&hs2[r]==hs2[l-1]?"YES":"NO");
}
}
return 0;
}
}
int main(){return asbt::main();}
H. [THUPC 2017] 欽妹的玩具商店
分塊，設塊長為 \(B\)，預處理 \(f_{l,r,x}\) 表示僅考慮 \([1,l]\cup[r,\frac{n}{B}]\) 中的玩具，花 \(x\) 元的最大愉悅度。詢問時向 \(f_{bel_l-1,bel_r+1}\) 中加入 \(l\) 和 \(r\) 所在塊內的玩具即可。\(bel_l\) 表示 \(l\) 所在塊。
使用二進制優化多重背包，分析時間復雜度：
- 預處理 \(O(\frac{n^2m\log{n}}{B})\)
- 詢問 \(O(qmB\log{n})\)
令 \(B=\sqrt{n}\)，時間復雜度為 \(O((n+q)m\sqrt{n}\log{n})\)，空間復雜度 \(O(nm)\)。
Code
#include<bits/stdc++.h>
#define int long long
#define il inline
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=1e3+5,maxm=40,mod=1e8+7;
int T,n,m,q,blen,bnum;
int a[maxn],b[maxn],c[maxn];
int bel[maxn],st[maxm],ed[maxm];
struct DP{
int f[maxn];
il void init(){
for(int i=0;i<=m;i++){
f[i]=0;
}
}
il int operator[](int x){
return f[x];
}
il void upd(int x){
int a=asbt::a[x],b=asbt::b[x],c=asbt::c[x];
for(int i=1;i<=c;i<<=1){
for(int j=m;j>=i*a;j--){
f[j]=max(f[j],f[j-i*a]+i*b);
}
c-=i;
}
for(int i=m;i>=c*a;i--){
f[i]=max(f[i],f[i-c*a]+c*b);
}
}
}dp[maxm][maxm];
il void solve(){
cin>>n>>m>>q;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
cin>>b[i];
}
for(int i=1;i<=n;i++){
cin>>c[i];
}
blen=sqrt(n);
bnum=(n+blen-1)/blen;
for(int i=1;i<=bnum;i++){
st[i]=ed[i-1]+1;
ed[i]=min(ed[i-1]+blen,n);
for(int j=st[i];j<=ed[i];j++){
bel[j]=i;
}
}
for(int i=0;i<=bnum;i++){
if(!i){
dp[i][bnum+1].init();
}
else{
dp[i][bnum+1]=dp[i-1][bnum+1];
for(int j=st[i];j<=ed[i];j++){
dp[i][bnum+1].upd(j);
}
}
for(int j=bnum;j>i;j--){
dp[i][j]=dp[i][j+1];
for(int k=st[j];k<=ed[j];k++){
dp[i][j].upd(k);
}
}
}
int ans1=0,ans2=0;
while(q--){
int l,r;
cin>>l>>r;
l=(l+ans1-1)%n+1;
r=(r+ans1-1)%n+1;
if(l>r){
swap(l,r);
}
DP ans=dp[bel[l]-1][bel[r]+1];
for(int i=st[bel[l]];i<l;i++){
ans.upd(i);
}
for(int i=ed[bel[r]];i>r;i--){
ans.upd(i);
}
ans1=ans2=0;
for(int i=1;i<=m;i++){
ans1+=ans[i];
ans2^=ans[i];
}
ans1%=mod;
cout<<ans1<<" "<<ans2<<"\n";
}
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
signed main(){
// cout<<cplx::usdmem();
ios::sync_with_stdio(0),cin.tie(0);
cin>>T;
while(T--){
solve();
}
return 0;
}
}
signed main(){return asbt::main();}
I. [SNOI2017]一個簡單的詢問
\(
\quad\sum{\operatorname{get}(l_1,r_1,x)\times\operatorname{get}(l_2,r_2,x)}\\
=\sum\operatorname{get}(1,l_1-1,x)\times\operatorname{get}(1,l_2-1,x)+\operatorname{get}(1,r_1,x)\times\operatorname{get}(1,r_2,x)-\operatorname{get}(1,l_1-1,x)\times\operatorname{get}(1,r_2,x)-\operatorname{get}(1,l_2-1,x)\times\operatorname{get}(1,r_1,x)
\)
將一個詢問拆成 \(4\) 個，莫隊給 \(l\) 指針和 \(r\) 指針各開一個桶即可。
Code
#include<bits/stdc++.h>
#define int long long
#define il inline
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=5e4+5;
int n,m,a[maxn],ans[maxn];
int blen,bel[maxn],tot;
int bucl[maxn],bucr[maxn];
struct wnti{
int l,r,id;
wnti(int l=0,int r=0,int id=0):l(l),r(r),id(id){}
il bool operator<(const wnti &x)const{
if(bel[l]==bel[x.l]){
return bel[l]&1?r>x.r:r<x.r;
}
return l<x.l;
}
}wt[maxn<<2];
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
cin>>m;
for(int i=1,l1,r1,l2,r2;i<=m;i++){
cin>>l1>>r1>>l2>>r2;
wt[++tot]=wnti(l1-1,l2-1,i);
wt[++tot]=wnti(r1,r2,i);
wt[++tot]=wnti(l1-1,r2,-i);
wt[++tot]=wnti(l2-1,r1,-i);
}
blen=n/sqrt(tot)+1;
for(int i=0;i<=n;i++){
bel[i]=i/blen;
}
sort(wt+1,wt+tot+1);
int l=0,r=0,res=0;
for(int i=1;i<=tot;i++){
while(l<wt[i].l){
bucl[a[++l]]++;
res+=bucr[a[l]];
}
while(r<wt[i].r){
bucr[a[++r]]++;
res+=bucl[a[r]];
}
while(l>wt[i].l){
res-=bucr[a[l]];
bucl[a[l--]]--;
}
while(r>wt[i].r){
res-=bucl[a[r]];
bucr[a[r--]]--;
}
if(wt[i].id>0){
ans[wt[i].id]+=res;
}
else{
ans[-wt[i].id]-=res;
}
}
for(int i=1;i<=m;i++){
cout<<ans[i]<<"\n";
}
return 0;
}
}
signed main(){return asbt::main();}
J. XOR and Favorite Number
考慮如何計算區間 \([l,r]\) 的異或和，顯然做一個前綴異或和 \(pre\)，答案即為 \(pre_r\oplus pre_{l-1}\)。那么在進行莫隊時，設新增了一個 \(pre\) 值為 \(x\) 的點，那么對答案的貢獻即為當前統計的 \(x\oplus k\) 的數量。時間復雜度 \(O(n\sqrt{m})\)。
Code
#include<bits/stdc++.h>
#define int long long
#define il inline
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=(1<<20)+5;
int n,m,k,blen;
int a[maxn],buc[maxn];
int ans[maxn],bel[maxn];
struct wnti{
int l,r,id;
il bool operator<(const wnti &x)const{
if(bel[l]==bel[x.l]){
return bel[l]&1?r>x.r:r<x.r;
}
return l<x.l;
}
}wt[maxn];
il void add(int x,int &res){
res+=buc[x^k];
buc[x]++;
}
il void del(int x,int &res){
buc[x]--;
res-=buc[x^k];
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
a[i]^=a[i-1];
}
for(int i=1;i<=m;i++){
cin>>wt[i].l>>wt[i].r;
wt[i].id=i;
}
blen=max(n/sqrt(m),1.0);
for(int i=1;i<=n;i++){
bel[i]=i/blen;
}
sort(wt+1,wt+m+1);
int l=1,r=0,res=0;
buc[0]=1;
for(int i=1;i<=m;i++){
// cout<<wt[i].l<<" "<<wt[i].r<<" "<<wt[i].id<<"\n";
while(l>wt[i].l){
add(a[--l-1],res);
}
while(r<wt[i].r){
add(a[++r],res);
}
// cout<<res<<"\n";
while(l<wt[i].l){
del(a[l++-1],res);
}
while(r>wt[i].r){
del(a[r--],res);
}
ans[wt[i].id]=res;
}
for(int i=1;i<=m;i++){
cout<<ans[i]<<"\n";
}
return 0;
}
}
signed main(){return asbt::main();}
/*
50 2 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
17 35
3 35
*/
K. String Set Queries
考慮所有集合內的字符串的不同長度不會超過 \(\sqrt{\sum|s_i|}\)，因此直接枚舉所有長度，哈希即可。時間復雜度 \(O(n\sqrt{n}\log{n})\)。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define ull unsigned ll
#define mp make_pair
#define pii pair<int,int>
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=3e5+5;
const ull bas1=13331;
const ll bas2=13327,mod2=1e9+7;
int n;
ull ha1[maxn],pw1[maxn];
ll ha2[maxn],pw2[maxn];
char s[maxn];
map<int,int> clen;
map<pair<ull,ll>,int> cha;
il ull gha1(int l,int r){
return ha1[r]-ha1[l-1]*pw1[r-l+1];
}
il ll gha2(int l,int r){
return (ha2[r]-ha2[l-1]*pw2[r-l+1]%mod2+mod2)%mod2;
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
pw1[0]=pw2[0]=1;
for(int i=1;i<=3e5;i++){
pw1[i]=pw1[i-1]*bas1;
pw2[i]=pw2[i-1]*bas2%mod2;
}
scanf("%d",&n);
while(n--){
int opt,len;
scanf("%d %s",&opt,s+1);
len=strlen(s+1);
switch(opt){
case 1:{
ull ha1=0;
ll ha2=0;
for(int i=1;i<=len;i++){
ha1=ha1*bas1+s[i];
ha2=(ha2*bas2+s[i])%mod2;
}
clen[len]++;
cha[mp(ha1,ha2)]++;
break;
}
case 2:{
ull ha1=0;
ll ha2=0;
for(int i=1;i<=len;i++){
ha1=ha1*bas1+s[i];
ha2=(ha2*bas2+s[i])%mod2;
}
if(--clen[len]==0){
clen.erase(len);
}
if(--cha[mp(ha1,ha2)]==0){
cha.erase(mp(ha1,ha2));
}
break;
}
default:{
int res=0;
for(int i=1;i<=len;i++){
ha1[i]=ha1[i-1]*bas1+s[i];
ha2[i]=(ha2[i-1]*bas2+s[i])%mod2;
}
for(pii i:clen){
for(int l=1,r=i.first;r<=len;l++,r++){
res+=cha[mp(gha1(l,r),gha2(l,r))];
}
}
printf("%d\n",res);
fflush(stdout);
break;
}
}
}
return 0;
}
}
int main(){return asbt::main();}
浙公網安備 33010602011771號