rt.
7.15：
晚上 6:00 到校。预习网络流并打了板子。
7.16：
树上启发式合并。
7.17：
二项式反演、min-max 容斥。
P4921 [MtOI2018] 情侣？给我烧了！
简单二项式反演练习题。
点击查看代码
#include<bits/stdc++.h>
#define int long longusing namespace std;const int Size=(1<<20)+1;
char buf[Size],*p1=buf,*p2=buf;
char buffer[Size];
int op1=-1;
const int op2=Size-1;
#define getchar() \
(tt == ss && (tt=(ss=In)+fread(In, 1, 1 << 20, stdin), ss == tt) \? EOF \: *ss++)
char In[1<<20],*ss=In,*tt=In;
inline int read()
{int x=0,c=getchar(),f=0;for(;c>'9'||c<'0';f=c=='-',c=getchar());for(;c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+(c^48);return f?-x:x;
}
inline void write(int x)
{if(x<0) x=-x,putchar('-');if(x>9) write(x/10);putchar(x%10+'0');
}const int N=2e3+5,mod=998244353;
int f[N+10],g[N+10];
int ksm(int x,int p)
{int ans=1;while(p){if(p&1) ans*=x,ans%=mod;x*=x;x%=mod;p>>=1;}return ans;
}
int C(int n,int m) { return f[n]*g[m]%mod*g[n-m]%mod; }
int A(int n,int m) { return f[n]*g[n-m]%mod; }int ans1[N+10][N+10],ans2[N+10];
int n;void solve()
{cin>>n;for(int i=0;i<=n;i++){cout<<((f[n]*f[n]%mod*ksm(2,i)%mod*g[i]%mod*ans1[n-i][n-i]%mod)+mod)%mod<<"\n";}
}signed main()
{f[0]=g[0]=1;for(int i=1;i<=N;i++) {f[i]=f[i-1]*i%mod;g[i]=g[i-1]*ksm(i,mod-2)%mod;}for(int up=0;up<=N;up++)for(int k=0;k<=N;k++){if(up-k<0) continue;ans1[up][k]=ksm(-2,k)*f[up*2-k*2]%mod*g[k]%mod*g[up-k]%mod*g[up-k]%mod;}for(int up=0;up<=N;up++)for(int k=1;k<=N;k++){if(up-k<0) continue;ans1[up][k]+=ans1[up][k-1];ans1[up][k]%=mod;}int T;cin>>T;while(T--) solve();//mt19937_64 myrand(time(0));return 0;
}/*722842020
138317470
921559819
359647162
687141626
346118686
625222092
542337323
886269899
944317174
460589718
811540952
20786512
387585883
469474953
548906529
871917136
778406107
569092611
800860
337514426
801633802
312159821
93444031
90542578
825940975
20000024
785199061
994585930
350128415
862900103
883162129
629959277
739204290
608293632
540950158
124289136
363286358
857308713
384746793
879153927
556173190
857677375
450955017
531591432
982819172
933001092
512595394
933070829
778961352
480009603
935286090
105123621
516375897
160958344
204402744
637758029
908640277
787972008
445923251
492507983
985429386
29082706
94289639
34604091
711283065
939587034
126262080
669499437
878972708
514361506
937924966
291237852
663298724
343816962
638919380
172534971
236170058
706172886
424787480
245248445
723990161
640745596
366740992
355944213
91835749
762422232
498310831
523709105
952955025
758565254
813416457
223906298
527918435
873083460
700091485
275169024
813932544
367384406
98485087
255154139
291410572
875700873
575067313
225892744
728391529
382628520
430033891
424258091
681971977
309495248
900585846
444259669
144328395
497755102
105359049
414357189
501715013
164613658
223170445
595298490
422835443
593597720
875654288
284387774
489562371
482264304
238514139
782091429
164339473
863532562
866250331
643349175
878646607
738273646
27863113
411315395
439803440
782881118
218418857
609619595
724811521
78633262
207988400
504696797
972193769
457708548
940592292
45742516
286866804
79443616
241157958
629915495
804238514
609548941
876247363
338354111
235891198
76205581
784179371
882966638
692354778
857926608
767375468
241164071
494388844
32769290
80892207
627156221
765688243
78524214
519630931
319011152
98684160
305160774
116478813
960434372
112669762
458641843
378309944
870208877
161585052
638364192
641094443
34192556
292431309
855793216
406164415
779379568
167904527
76458518
450512519
387093597
515624040
689883306
820096400
769832610
764317094
534074955
343150200
884048630
418840080
339348891
420417480
265388714
955231917
584293377
168817667
284226287
306777235
146035273
710214882
137785837
130407642
214592951
506563950
503410027
126477417
643999908
642785186
986853015
370695720
852860359
962946253
430988776
791048346
69543110
178854306
183142415
589674406
599255805
15174494
825164427
78990849
842232350
430597019
432697055
406619683
486926560
701430448
433984620
548568248
844174810
570957603
177800111
13377421
78401592
286853293
939821381
509288814
430953495
249086281
720976054
799266140
736711201
418258741
254956950
306035317
599715097
752070223
776986725
689180513
16742228
480771114
2927903
445260862
157011363
225336428
477455530
211970956
49179733
748627454
519167637
377372573
725662056
255023909
128593679
465290478
178234348
186912204
750214431
733907416
602138568
972271415
823746778
684973983
234639199
352049987
654813174
720489232
859900739
406591055
454869456
0
918846203722842020
138317470
987752262
359647162
687141626
346118686
625222092
542337323
886269899
944317174
460589718
811540952
20786512
387585883
469474953
548906529
871917136
778406107
569092611
800860
337514426
801633802
312159821
93444031
90542578
825940975
20000024
785199061
994585930
350128415
862900103
883162129
629959277
739204290
608293632
540950158
124289136
363286358
857308713
384746793
879153927
556173190
857677375
450955017
531591432
982819172
933001092
512595394
933070829
778961352
480009603
935286090
105123621
516375897
160958344
204402744
637758029
908640277
787972008
445923251
492507983
985429386
29082706
94289639
34604091
711283065
939587034
126262080
669499437
878972708
514361506
937924966
291237852
663298724
343816962
638919380
172534971
236170058
706172886
424787480
245248445
723990161
640745596
366740992
355944213
91835749
762422232
498310831
523709105
952955025
758565254
813416457
223906298
527918435
873083460
700091485
275169024
813932544
367384406
98485087
255154139
291410572
875700873
575067313
225892744
728391529
382628520
430033891
424258091
681971977
309495248
900585846
444259669
144328395
497755102
105359049
414357189
501715013
164613658
223170445
595298490
422835443
593597720
875654288
284387774
489562371
482264304
238514139
782091429
164339473
863532562
866250331
643349175
878646607
738273646
27863113
411315395
439803440
782881118
218418857
609619595
724811521
78633262
207988400
504696797
972193769
457708548
940592292
45742516
286866804
79443616
241157958
629915495
804238514
609548941
876247363
338354111
235891198
76205581
784179371
882966638
692354778
857926608
767375468
241164071
494388844
32769290
80892207
627156221
765688243
78524214
519630931
319011152
98684160
305160774
116478813
960434372
112669762
458641843
378309944
870208877
161585052
638364192
641094443
34192556
292431309
855793216
406164415
779379568
167904527
76458518
450512519
387093597
515624040
689883306
820096400
769832610
764317094
534074955
343150200
884048630
418840080
339348891
420417480
265388714
955231917
584293377
168817667
284226287
306777235
146035273
710214882
137785837
130407642
214592951
506563950
503410027
126477417
643999908
642785186
986853015
370695720
852860359
962946253
430988776
791048346
69543110
178854306
183142415
589674406
599255805
15174494
825164427
78990849
842232350
430597019
432697055
406619683
486926560
701430448
433984620
548568248
844174810
570957603
177800111
13377421
78401592
286853293
939821381
509288814
430953495
249086281
720976054
799266140
736711201
418258741
254956950
306035317
599715097
752070223
776986725
689180513
16742228
480771114
2927903
445260862
157011363
225336428
477455530
211970956
49179733
748627454
519167637
377372573
725662056
255023909
128593679
465290478
178234348
186912204
750214431
733907416
602138568
972271415
823746778
684973983
234639199
352049987
654813174
720489232
859900739
406591055
454869456
0
918846203*/
7.18：
可持久化线段树、平衡树、字典树。
SP11470 TTM - To the moon
区间修改可持久化线段树板子。
代码只可持久化了懒标记。
点击查看代码
#include<bits/stdc++.h>
#define int long longusing namespace std;const int N=1e5+5;
int n,m;
int a[N],f[N];
// dt: ；子树里的 add 总和
// lazy : 该区间懒标记
struct Tree{int dt,lazy;int lp,rp;
}t[N*500];//n log_n log_(n log_n)
int tot;
int root[N];int add(int l,int r,int sl,int sr,int k,int lastp,int &nwp)
{if(!nwp) nwp=++tot;if(sl<=l&&r<=sr){t[nwp]={t[lastp].dt+k*(r-l+1),t[lastp].lazy+k,t[lastp].lp,t[lastp].rp};// cerr<<l<<" "<<r<<" "<<sl<<" "<<sr<<" k="<<k<<" len="<<r-l+1<<" ";
// cerr<<"t[nwp].lazy="<<t[nwp].lazy<<" t[nwp].dt="<<t[nwp].dt<<" ";
// cerr<<"t[lastp].lazy="<<t[lastp].lazy<<" t[lastp].dt="<<t[lastp].dt<<"\n";return k*(r-l+1);}int mid=(l+r)>>1,dt=0;if(sl<=mid) dt=add(l,mid,sl,sr,k,t[lastp].lp,t[nwp].lp);else t[nwp].lp=t[lastp].lp;if(sr>mid) dt+=add(mid+1,r,sl,sr,k,t[lastp].rp,t[nwp].rp);else t[nwp].rp=t[lastp].rp;t[nwp].lazy=t[lastp].lazy;t[nwp].dt=t[lastp].dt+dt;
// cerr<<l<<" "<<r<<" "<<sl<<" "<<sr<<" ";
// cerr<<"t[nwp].lazy="<<t[nwp].lazy<<" t[nwp].dt="<<t[nwp].dt<<"\n";return dt;
}// pair<int,int> operator+(const pair<int,int> &x,const pair<int,int> &y)
// {
// pair<int,int> ans=make_pair(0,0);
// ans.first=x.first+y.first;
// ans.second=x.second+y.second;
// return ans;
// }int find(int l,int r,int sl,int sr,int nw_lazy,int p)
{if(sl<=l&&r<=sr){// cout<<"l="<<l<<" r="<<r<<" sl="<<sl<<" sr="<<sr<<" dt="<<t[p].dt<<" lazy="<<nw_lazy*(r-l+1)<<"\n";return t[p].dt+nw_lazy*(r-l+1);}int mid=(l+r)>>1,ans=0;if(sl<=mid) ans+=find(l,mid,sl,sr,nw_lazy+t[p].lazy,t[p].lp);if(sr>mid) ans+=find(mid+1,r,sl,sr,nw_lazy+t[p].lazy,t[p].rp);
// cout<<"l="<<l<<" r="<<r<<" sl="<<sl<<" sr="<<sr<<" ans="<<ans<<"\n";return ans;// pair<int,int> ans=make_pair(0,0);
}int query(int l,int r,int t)
{
// cout<<root[t]<<"\n";return find(1,n,l,r,0,root[t]);
}signed main()
{// freopen("a.in","r",stdin);ios::sync_with_stdio(0);cin>>n>>m;for(int i=1;i<=n;i++) cin>>a[i],f[i]=f[i-1]+a[i];
// return 0;int nw=0;while(m--){char op;int l,r,d,t;cin>>op;if(op=='C'){cin>>l>>r>>d;nw++;add(1,n,l,r,d,root[nw-1],root[nw]);}if(op=='Q'){cin>>l>>r;cout<<query(l,r,nw)+f[r]-f[l-1]<<"\n";}if(op=='H'){cin>>l>>r>>t;cout<<query(l,r,t)+f[r]-f[l-1]<<"\n";}if(op=='B'){cin>>t;for(int j=t+1;j<=nw;j++) root[j]=0;nw=t;}}//mt19937_64 myrand(time(0));return 0;
}/*
10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4*/
P4098 [HEOI2013] ALO
简单可持久化字典树应用。
写了四个二分。
点击查看代码
#include<bits/stdc++.h>
#define int long longusing namespace std;inline int read()
{int x=0,c=getchar(),f=0;for(;c>'9'||c<'0';f=c=='-',c=getchar());for(;c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+(c^48);return f?-x:x;
}
inline void write(int x)
{if(x<0) x=-x,putchar('-');if(x>9) write(x/10);putchar(x%10+'0');
}bool num[50100][36];
int n;
int a[50100];
int st[17][50100];
int logn[50100];
int ksm[65]={};
int root[50100];
int tot;
struct Tree{int lp,rp,cnt;
}t[50100*34*2];
void add(int id,int pos,int lastp,int &p)
{if(pos>34) return;if(!p) p=++tot;t[p].cnt=t[lastp].cnt+1;if(num[id][pos+1]==0){add(id,pos+1,t[lastp].lp,t[p].lp);t[p].rp=t[lastp].rp;}else {add(id,pos+1,t[lastp].rp,t[p].rp);t[p].lp=t[lastp].lp;}// t[p].cnt=t[t[p].lp].cnt+t[t[p].rp].cnt;
}void chai(int id)
{int cnt=0,x=a[id];while(x) {// cerr<<"cnt="<<cnt<<"\n";num[id][++cnt]=(x&1);x>>=1;}for(int i=34,j=1;i>j;i--,j++) swap(num[id][j],num[id][i]);add(id,0,root[id-1],root[id]);
}int query(int l,int r)
{int k=logn[r-l+1];return max(st[k][l],st[k][r-(1<<k)+1]);
}int xorrr(int id,int lp,int rp,long long dt)
{int ans=0;// if(pos>34) return 0;for(int pos=1;pos<=34;pos++){int c[2]={};c[0]=t[t[rp].lp].cnt-t[t[lp].lp].cnt;c[1]=t[t[rp].rp].cnt-t[t[lp].rp].cnt;if(c[1^num[id][pos]]){// cout<<(1^num[id][pos]);ans+=dt;if(num[id][pos]==0) lp=t[lp].rp,rp=t[rp].rp;else lp=t[lp].lp,rp=t[rp].lp;}else if(num[id][pos]==0) lp=t[lp].lp,rp=t[rp].lp;//,cout<<num[id][pos];else lp=t[lp].rp,rp=t[rp].rp;//,cout<<num[id][pos];dt>>=1;}// cout<<"\n";return ans;// int lp=t[t[nwp].lp].cnt,rp=;}int find(int nw_p)
{int pl1=nw_p-1;// if(pl1>=1)for(int k=logn[pl1];k>=0;k--)if(pl1-ksm[k]>0&&query(pl1-ksm[k],pl1)<a[nw_p]) pl1-=ksm[k];if(a[pl1]>=a[nw_p]||pl1<1) pl1++;int pr1=nw_p+1;if(pr1<=n)for(int k=logn[n-nw_p];k>=0;k--)if(pr1+ksm[k]<=n&&query(pr1,pr1+ksm[k])<a[nw_p]) pr1+=ksm[k];if(a[pr1]>=a[nw_p]||pr1>n) pr1--;// cout<<"pl1="<<pl1<<" pr1="<<pr1<<"\n";int ans=0;if(pl1>1){int pl2=pl1-2;if(pl2>0&&a[pl2]<a[nw_p]){for(int k=logn[pl2];k>=0;k--)if(pl2-ksm[k]>0&&query(pl2-ksm[k],pl2)<a[nw_p]) pl2-=ksm[k];}else pl2++;// cout<<"left ["<<pl2<<","<<pr1<<"] nw="<<nw_p<<"\n";ans=xorrr(nw_p,root[pl2-1],root[pr1],ksm[33]);}if(pr1<n){int pr2=pr1+2;if(pr2<=n&&a[pr2]<a[nw_p]){for(int k=logn[n-pr2+1];k>=0;k--)if(pr2+ksm[k]<=n&&query(pr2,pr2+ksm[k])<a[nw_p]) pr2+=ksm[k];}else pr2--;// cout<<"right ["<<pl1<<","<<pr2<<"] nw="<<nw_p<<"\n";ans=max(ans,xorrr(nw_p,root[pl1-1],root[pr2],ksm[33]));}return ans;// p--;// a_i \belongs [p,l), a_i< a_r
}signed main()
{n=read();for(int i=1;i<=n;i++) a[i]=read(),st[0][i]=a[i];logn[1]=0;ksm[0]=1;for(int i=1;i<=40;i++) ksm[i]=ksm[i-1]<<1;for(int i=2;i<=n+10;i++) logn[i]=logn[i>>1]+1;for(int j=1;j<=logn[n];j++)for(int i=1;i<=n;i++)st[j][i]=max(st[j-1][i],st[j-1][i+(1<<(j-1))]);for(int i=1;i<=n;i++) chai(i);int ans=0;for(int i=1;i<=n;i++) ans=max(ans,find(i));cout<<ans;return 0;
}
P4735 最大异或和
纯板子。
点击查看代码
#include<bits/stdc++.h>
#define int long longusing namespace std;inline int read()
{int x=0,c=getchar(),f=0;for(;c>'9'||c<'0';f=c=='-',c=getchar());for(;c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+(c^48);return f?-x:x;
}
inline void write(int x)
{if(x<0) x=-x,putchar('-');if(x>9) write(x/10);putchar(x%10+'0');
}const int N=9e5+10;
bool num[N][36];
int n;
int a[N];
int st[17][N];
int logn[N];
int ksm[65]={};
int root[N];
int tot;
struct Tree{int lp,rp,cnt;
}t[N*30*3];
// int sum[1<<20];
void add(int id,int pos,int lastp,int &p)
{if(pos>30) return;if(!p) p=++tot;t[p].cnt=t[lastp].cnt+1;if(num[id][pos+1]==0){add(id,pos+1,t[lastp].lp,t[p].lp);t[p].rp=t[lastp].rp;}else {add(id,pos+1,t[lastp].rp,t[p].rp);t[p].lp=t[lastp].lp;}// t[p].cnt=t[t[p].lp].cnt+t[t[p].rp].cnt;
}void chai(int id)
{int cnt=0;int x=a[id];while(x) {num[id][++cnt]=(x&1);x>>=1;}for(int i=30,j=1;i>j;i--,j++) swap(num[id][j],num[id][i]);
}int xorrr(int id,int lp,int rp,long long dt)
{int ans=0;// if(pos>30) return 0;for(int pos=1;pos<=30;pos++){int c[2]={};// cout<<"lp="<<lp<<" rp="<<rp<<"\n";c[0]=t[t[rp].lp].cnt-t[t[lp].lp].cnt;c[1]=t[t[rp].rp].cnt-t[t[lp].rp].cnt;// cout<<"pos="<<pos<<" c[0]="<<c[0]<<" c[1]="<<c[1]<<"\n";if(c[1^num[id][pos]]){// cout<<1;ans+=dt;if(num[id][pos]==0) lp=t[lp].rp,rp=t[rp].rp;else lp=t[lp].lp,rp=t[rp].lp;}else if(num[id][pos]==0) lp=t[lp].lp,rp=t[rp].lp;//,cout<<0;else lp=t[lp].rp,rp=t[rp].rp;//,cout<<0;dt>>=1;}// cout<<"\n";return ans;// int lp=t[t[nwp].lp].cnt,rp=;}// int find(int nw_p)
// {
// int pl1=nw_p-1;
// // if(pl1>=1)
// for(int k=logn[pl1];k>=0;k--)
// if(pl1-ksm[k]>0&&query(pl1-ksm[k],pl1)<a[nw_p]) pl1-=ksm[k];
// if(a[pl1]>=a[nw_p]||pl1<1) pl1++;// int pr1=nw_p+1;
// if(pr1<=n)
// for(int k=logn[n-nw_p];k>=0;k--)
// if(pr1+ksm[k]<=n&&query(pr1,pr1+ksm[k])<a[nw_p]) pr1+=ksm[k];
// if(a[pr1]>=a[nw_p]||pr1>n) pr1--;// // cout<<"pl1="<<pl1<<" pr1="<<pr1<<"\n";
// int ans=0;
// if(pl1>1)
// {
// int pl2=pl1-2;
// if(pl2>0&&a[pl2]<a[nw_p])
// {
// for(int k=logn[pl2];k>=0;k--)
// if(pl2-ksm[k]>0&&query(pl2-ksm[k],pl2)<a[nw_p]) pl2-=ksm[k];
// }
// else pl2++;
// // cout<<"left ["<<pl2<<","<<pr1<<"] nw="<<nw_p<<"\n";
// ans=xorrr(nw_p,root[pl2-1],root[pr1],ksm[33]);
// }
// if(pr1<n)
// {
// int pr2=pr1+2;
// if(pr2<=n&&a[pr2]<a[nw_p])
// {
// for(int k=logn[n-pr2+1];k>=0;k--)
// if(pr2+ksm[k]<=n&&query(pr2,pr2+ksm[k])<a[nw_p]) pr2+=ksm[k];
// }
// else pr2--;
// // cout<<"right ["<<pl1<<","<<pr2<<"] nw="<<nw_p<<"\n";
// ans=max(ans,xorrr(nw_p,root[pl1-1],root[pr2],ksm[33]));
// }
// return ans;
// // p--;
// // a_i \belongs [p,l), a_i< a_r
// }signed main()
{int n,m,tot=6e5;n=read();m=read();ksm[0]=1;for(int i=1;i<=40;i++) ksm[i]=ksm[i-1]*2;add(0,0,0,root[0]);for(int i=1;i<=n;i++) a[i]=read()^a[i-1],chai(i),add(i,0,root[i-1],root[i]);//;,cout<<a[i]<<"\n"; while(m--){char op;cin>>op;if(op=='A'){int x=read();n++;a[n]=x^a[n-1];chai(n);add(n,0,root[n-1],root[n]);}else{int l=read(),r=read(),x=read()^a[n];a[++tot]=x;chai(tot);// cout<<"["<<l-1<<","<<r-1<<"]\n";// cout<<x<<"\n";cout<<xorrr(tot,root[l-2],root[r-1],ksm[29])<<"\n";}}return 0;
}
![[C++]内存管理：串顺序存储的内存回收](http://pic.xiahunao.cn/yaotu/[C++]内存管理：串顺序存储的内存回收)
