赛前错误总结
这里主要放一下模拟赛或者做题时犯的再犯就是找抽）。
1.Single Cut of Failure
看清输出是啥，如这题，输出一条直线的坐标，如果是两个点分开输出的，那么第一个点的坐标应该后面多一个空格，如果输出有多种情况，需分类讨论的话，不要忘了把每个输出后都加个空格。
void solve(double p){
if(p<=h){printf("0 %.2lf ",p);return ;}
if(p<=w+h){printf("%.2lf %.2lf ",p-h,h);return ;}
if(p<=2*h+w){printf("%.2lf %.2lf ",w,2.0*h+w-p);return ;}
printf("%.2lf 0 ",2.0*h+2.0*w-p);return ;
}
2.随机游走
注意，带有循环节的东西往往前面还有不符合循环节规律的一段数字。（循环节前还有一段小尾巴）记得判掉。
for(int i=0;i<m;i++) f[i]=(i+calc(i))%m;
while(vis[a]==0){
vis[a]=++tot,rd[tot]=a;a=f[a];
}
if(n<=tot) printf("%lld\n",rd[n]);
else{
n=n-vis[a];
printf("%lld\n",rd[n%(tot-vis[a]+1)+vis[a]]);
}3.Exam Results
注意从大到小排序完，双指针寻找最长合法区间时，要注意有没有人的最好分数和最坏分数都比当前最大值大，即它在当前的区间内没有分数，要直接break掉。
if(cnt>ans) ans=cnt;
vis[c[i].id]--,wc[c[i].id]--;
if(!vis[c[i].id]) cnt--;
if(!wc[c[i].id]) break;
4.magic
100分白给，呜呼！ 二分里上下界调对了，特判里的上界忘改了，而且这还是个没用的特判，去掉特判就过了。。。。
int l=1,r=min(n,(int)p),ans=-1;
if(sum[n]*p-cd(2,min(n,(int)p))<q) printf("-1\n");
min(n,(int)p)!!!!!!!
5.Cow Hopscotch G
分治时把l写成1，我是不是傻。。。 题目说要取模，结果没模的交了一发，白给94分。。。。
for(int i=l;i<=mid;i++){
if(ct[a[i][j]]<cnt) ct[a[i][j]]=cnt,s[a[i][j]]=0;
(all+=f[i][j])%=mod,(s[a[i][j]]+=f[i][j])%=mod;
}6.Choosing Balls
用同颜色和异色的最大值更新。每次而外维护最大的两个颜色的dp值，每个颜色至少与最大值和次大值中一个不同。注意更新最大值的时候先判一下是否与最大值颜色相同，如果相同，那么要continue掉，不然的话se=fi与fi颜色相同了。
if(fi==c[i]) continue;
if(p[c[i]]>p[fi]) se=fi,fi=c[i];
else if(p[c[i]]>p[se]) se=c[i];
7.毛毛虫
首先输入一个点时只有1个点也能构成毛毛虫。
第二点，一条链的时候并不是由两个子节点的链拼接而成，用
ans=max(ans,f[p]+f[v]+siz-2); 会出错。对于以一个点为顶点的链的答案要单独更新ans
ans=1;//初始化
//dfs部分内容
for(int i=head[u];i!=-1;i=g[i].nxt){
int v=g[i].to;if(v==fa) continue;
dfs(v,u);f[u]=max(f[u],f[v]+siz-1-(fa!=0));
ans=max(ans,f[p]+f[v]+siz-2);
if(f[v]>f[p]) p=v;
}
ans=max(ans,f[u]);8.重建道路
本来就是一道树上背包的大水题，我硬是调了老久，还重构了一遍。。。
错误原因：
1.联通不连通没考虑清楚
2.树上背包时如果每个都要加一遍的话，建议新开一个数组，但是，这个数组必须要有一维
u 表示在哪个节点，不然的话只有一维数组会导致在递归时会被改变，导致错误。3.用新数组将答案更新时，注意要先
siz[u]+=siz[v] ，不然的话有些节点答案更新不到。
正确写法：
void dfs(int u,int fa){
siz[u]=1,f[u][1]=0;
for(int i=head[u];i!=-1;i=g[i].nxt){
int v=g[i].to;if(v==fa) continue;
dfs(v,u);
for(int j=min(m,siz[u]);j>=0;j--)
for(int k=min(m,siz[v]);k>=0;k--){
p[u][j+k]=min(p[u][j+k],f[u][j]+f[v][k]);
}
siz[u]+=siz[v];
for(int j=siz[u];j>=0;j--){
f[u][j]=p[u][j],p[u][j]=p[u][n+3];
}
}
f[u][0]=1;
}错误写法
void dfs(int u,int fa){
siz[u]=1,f[u][1]=0;
for(int i=head[u];i!=-1;i=g[i].nxt){
int v=g[i].to;if(v==fa) continue;
dfs(v,u);
for(int j=min(m,siz[u]);j>=0;j--)
for(int k=min(m,siz[v]);k>=0;k--){
p[u][j+k]=min(p[u][j+k],f[u][j]+f[v][k]);
}
for(int j=siz[u];j>=0;j--){
f[u][j]=p[u][j],p[u][j]=p[u][n+3];
}
siz[u]+=siz[v];//错在这
}
f[u][0]=1;
}
错误写法
for(int i=head[u];i!=-1;i=g[i].nxt){
int v=g[i].to;if(v==fa) continue;
dfs(v,u);
for(int j=min(m,siz[u]);j>=0;j--)
for(int k=min(m,siz[v]);k>=0;k--){
p[j+k]=min(p[j+k],f[u][j]+f[v][k]);
//错在递归时可能也会把这个值更改，发生错误
//当然不加一维，写在这个for循环下面也是可以的
}
for(int j=siz[u];j>=0;j--)
f[u][j]=p[j],p[j]=p[n+3];
siz[u]+=siz[v];//错误1
}
9.CF1146F Leaf Partition
变量名写反，吐血。。。
void dfs(int u,int fa){
ll cnt0=1,cnt1=0,cnt2=0,cnt3=1;
for(int i=head[u];i!=-1;i=g[i].nxt){
int v=g[i].to;if(v==fa) continue;
dfs(v,u);
cnt2=(mul(cnt1,f[v][0])+mul(cnt2,(f[v][0]+f[v][1])%mod))%mod;
cnt1=(mul(cnt0,f[v][0])+mul(cnt1,f[v][1]))%mod;
cnt0=mul(cnt0,f[v][1]);
}
f[u][0]=(cnt1+cnt2)%mod,f[u][1]=(cnt2+cnt0)%mod;
if(head[u]==-1){f[u][1]=1,f[u][0]=1;return ;}
}10.靶形数独
数组越界不自知，（数组开小了）。。
隔壁教了我如何用c++的（不知道什么东西）来判断是否越界，加上 -Wall -Wextra -fsanitize=undefined 就可以了。
忘了原本就有一些数的贡献，还以为自己错了。
tot=0,bas=0;int wc=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(a[i][j]){
xx[i]|=(1<<a[i][j]);
yy[j]|=(1<<a[i][j]);
bl[num[i][j]]|=(1<<a[i][j]);
bas+=sc[i][j]*a[i][j];//原来就有贡献
}
else{
wc+=sc[i][j]*9;
id[++tot].ix=i,id[tot].iy=j;//数组越界的地方，显然空位不止N个
}
}
}11.物流运输
原本是一道水题，结果我硬是想着状压和预处理，导致Wa了几发，点数有
20 ，你预处理就要m\ast 2^m ,还不如每次更新时跑一遍dij快，dij堆优化后(m+ 边数) \log 边数 ，结合m 只有20 ，跑个n^2 遍都比预处理快多了，2^m 也不看看是多少，1048576 \ast 20 你光个预处理就T 了，以后不要想着点数少就状压，想想还可以暴力dij一遍图。
priority_queue<pii >q;//用pair的first比大小的性质，到该点的距离取负值，求最短路。（优先队列默认是大根堆）。
int dij(int x){
if(wc[x]!=-1) return wc[x];
while(!q.empty()) q.pop();
memset(dis,-1,sizeof(dis));
dis[1]=0;q.push(make_pair(0,1));
while(!q.empty()){
int u=q.top().second;q.pop();
for(int i=1;i<=m;i++)
if(g[u][i]!=-1&&(!((1<<(i-1))&x))){
if(dis[i]==-1||g[u][i]+dis[u]<dis[i]){
dis[i]=dis[u]+g[u][i];
q.push(make_pair(-dis[i],i));
}
}
}
wc[x]=dis[m];
return dis[m];
}
for(int i=1;i<=n;i++){
for(int j=0;j<i;j++){
if(dij(c[j+1][i])==-1) continue;
f[i]=Min(f[i],f[j]+dij(c[j+1][i])*(i-j)+k);
}
} 12.关于double类型的数组，如果用memset初始化为-1会出事，会变成-nan(怀疑赋为0x3f也有问题)
13.monsters
作为一道带悔贪心，它真的很套路。
首先1~n扫过去，我们能要的都要，当我们要不起的时候看看这个是否比之前的某个数更优（之前的每个点的消耗都放入一个大根堆里），判断是否进行替换即可。
BUT，算代价的时候，我用余数来判断x最少要打几次，但是漏判了余数为0，即y是可以整数次恰好打完的情况，这时候，x不能在最后抢人头了，必须抢在y的最后一次攻击前把怪物打爆，此时x要打(y-1)/x+1次。（在我的代码里，记录的是打到濒死状态需几步，即(y-1)/x次）
考后订题的时候，又忘了自己的记录的是什么，导致Wa了一发。
for(int i=1;i<=n;i++){
p[i].b=(a[i]-1)/y;
p[i].c=a[i]%y;
if(!p[i].c){p[i].c=(y-1)/x;continue;}
p[i].c=(p[i].c<=x?0:((p[i].c-1)/x));
p[i].id=i;
}14.[POI2014]PTA-Little Bird
首先这题能用单调队列优化仅仅是因为变化量为1，本题能用单调队列维护两个变量的原因仅仅是这个，有点失望。
它的式子是f[i]=min{f[j]+(a[i]>=a[j])},它要求在满足f的越小越好的同时，还要考虑a的变化，由于a的影响只能为1，所以，在满足f的大前提下满足a，由于我跳到更高的点会付出多的代价，所以i的转移点j的a值越大越好，所以你在f相同时维护的a值单调递减。
一开始我把转移点和跳到的点决策单调性搞混了，然后还没看出来，呜呼。
bool check(int i,int j){
return f[j]==f[i]?(a[j]>=a[i]):(f[j]<f[i]);
}15.可能会出错的点：差分不是前缀和，差分是原序列相邻两项的差，枚举顺序从后往前，而不是从前往后变成减去差分序列中的数。
如原序列a[1],a[2],a[3],a[4],
枚举顺序从后往前是a[1],a[2]-a[1],a[3]-a[2],a[4]-a[3]
从前往后枚举是a[1],a[2]-a[1],a[3]-(a[2]-a[1]),a[4]-(a[3]-(a[2]-a[1]))
代码实现小细节，千万别搞错。
16.阶乘漏取模，快速乘在最后漏取模。
ll mul(ll x,ll y){
x%=mod,y%=mod;x=(x+mod)%mod,y=(y+mod)%mod;ll p=y/mod2;
return (y%mod2*x%mod+(p*x)%mod*mod2%mod)%mod;//加起来可能超过模数，漏取模了。
}
for(int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%mod;//这里不取模，是个人才。
17.pastel
两个数组名写反。。
查询set内的每个元素的写法
for(set<int>::iterator it=s[x].begin();it!=s[x].end();++it)
for(int i=1;i<=num;i++) s[p].insert(pr[i]);
if(col[p]) break;p=pa[p];
//数组名写反翻车现场（此处已改正）
18.minnum
题目中要求最高2^i,i<p，代码中写成2^i,i<=p了。
for(int t=1;t<p;t++){//已改正
int c=t&1;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++) mp[c][i][j]=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)
for(int k=1;k<=n;k++){
if(mp[!c][j][i]&&mp[!c][i][k])
mp[c][j][k]=1,g[j][k]=1;
}
}
}19.independent
贪心做法没假，但我假了。。。
我是直接拿最下面的点搜k步然后把它标记，但是he姥爷说了贪心的错误原因是它有可能把一个覆盖，但是无法把所有它的子节点覆盖，它的子节点更新的时候仍会往上走，往上走遇到它就停止了，但是如果还有剩余步数可以让它更上一层楼，所以是我搜索的错。。
void getvis(int u,int stp){//假搜索
if(vis[u]) return ;vis[u]=1;//搜到就停了，但是我上面可能还可以被更新。
if(!stp) return ;
for(int i=head[u];i!=-1;i=g[i].nxt){
int v=g[i].to;if(vis[v]) continue;
getvis(v,stp-1);
}
}正确的搜索，错误的时间复杂度，脚造的数据，还是能过的（我...太菜了,打不动点分树）
void getvis(int u,int stp){
if(vis[u]>=stp) return ;vis[u]=stp;//记录步数
if(!stp) return ;
for(int i=head[u];i!=-1;i=g[i].nxt){
int v=g[i].to;
getvis(v,stp-1);
}
}
20.画画
什么阴间内存啊！！！！256MB，极有可能爆int，n有5000,要开
n^2 ，long long开不下n^2 转成int后一直爆int,一直WA
把每个加法，乘法改成函数，里面调用long long，发现取地址的变量必须是属于相同类型就是add(ll &x,ll y)，在调用add时，add(dp[i][j],p)必须满足dp[i][j]也是long long，因为取地址了。。。只好改成不取地址的那种多写几个等于号。
本地数组越界都不显示RE,交上评测时不断RE,自闭了。
改正以上错误就过了。。。。
int n,m,a[M],num[N];int dp[N][N],c[N][N];
ll add(ll x,ll y) {y%=mod;x+=y;x%=mod;if(x<0) x+=mod;return x;}
ll MOD(ll x) {return (x%mod+mod)%mod;}
ll Mul(ll x,ll y) {x%=mod;y%=mod;return (x*y)%mod;}
//写成函数的形式，里面写longlong，不担心爆int
//int 最大只能表示2147483647，不然就越界了，
//事实上，你两个小于998244353的数相加没问题，
//但相乘必须开long long，
//如果只写个1ll*x很容易挂，建议多写成函数的形式。
for(int i=0;i<=n;i++){
ll sum=0;
if(i) for(int k=1;k<=n;k++) c[i][k]=add(c[i][k],c[i-1][k]);
//枚举的时候i可以为0，然后c[i-1][k]中i-1变-1了，越界RE
for(int j=1;j<=n;j++) dp[i][j]=add(dp[i][j],c[i][j]);
if(i!=n){
for(int j=(i!=0);j<=n;j++)
sum=add(sum,Mul(dp[i][j],num[j]));
for(int k=1;k<=n;k++){
ll ad=MOD(sum-dp[i][k]);
c[i+1][k]=add(c[i+1][k],ad);
c[i+k+1][k]=MOD(c[i+k+1][k]-ad);
}
}
}
21.cutlet
这题部分转移倒序。且题面中给的
n 的范围是1e5 ，但实际上你输进来要2n 个数，数组漏开两倍，已经不止一次犯这错了。
const int N = 2e5+9;//题目中n<=1e5，但是要输入2n个数，时间点有2n个单调队列写的时候判l的时候里面写成了r
while(l<=r&&q[l]<j-(a[i].r-a[i].l)) l++;22.CF543D
普通换根题，但是由于long long溢出懵逼了很久。
一开始代码里写的是这样的。
(f[u][1]*=((2ll*f[v][0]%mod+f[v][1])%mod))%mod;但CF官网一直报符号溢出，但纠结的是我取模了啊。
直到仔细看了下代码。。。
这么下，发现
(x \ast =y) \% mod 是没有取模效果的，上次看某位大佬代码里有(x \ast =y) \% =mod 这种写法，就打算也沿用下去，今天发现了一个弊端，如果末尾漏打一个等于，它就没取模效果了。。
(f[u][1]*=((2ll*f[v][0]%mod+f[v][1])%mod))%=mod;23.Super Jader
没考虑建图是否必要，想是可以往建图那边想，但是真正跑时，一是建图上下左右四条边还有两条颜色边总共1e6个点，6e6条边，空间都爆炸了，dij复杂度(n+m) log m，每个颜色点都跑一遍跑不动的。
由于边权是1，跑bfs就行了，还有你想想对于一种颜色，它并不会通过这颜色两次，跑bfs的时候一种颜色最先穿越后，后面的就没必要通过该颜色穿越了(bfs每条边都是1，最先访问到的一定比后面的优)，虽然可能也会判掉，但是多比较几次总归超时了。
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
queue<int >q;
void bfs(int col){
int u=c[col];dis[col][u]=0;
while(!q.empty()) q.pop();
for(int i=head[u];i!=-1;i=g[i].nxt){
int v=g[i].to;q.push(v);
dis[col][v]=0;
}
memset(vis,0,sizeof(vis));vis[col]=1;
while(!q.empty()){
u=q.front();q.pop();
int x=(u-1)/m+1;int y=u-(x-1)*m;
if(x<=n&&x>=1&&y<=m&&y>=1){
for(int i=0;i<4;i++){
int nx=dx[i]+x,ny=dy[i]+y;
if(nx>n||nx<1||ny>m||ny<1) continue;
if(dis[col][pos(nx,ny)]==-1||dis[col][pos(nx,ny)]>dis[col][u]+1){
dis[col][pos(nx,ny)]=dis[col][u]+1;
q.push(pos(nx,ny));
}
}
}
if(vis[a[x][y]]) continue;vis[a[x][y]]=1;//防止重复颜色跑两遍
for(int i=head[c[a[x][y]]];i!=-1;i=g[i].nxt){
int v=g[i].to;
if(dis[col][v]==-1||dis[col][v]>dis[col][u]+1){
dis[col][v]=dis[col][u]+1;
q.push(v);
}
}
}
return ;
}24.分蛋糕
连add加边函数都写错了，呜呜呜。原本是想写蓝书tarjan那节介绍的在有重边情况下判断是否是无向图中的同一条边，即进来的边是不是i^1
结果写成了这样，错的离谱
void add(int u,int v){
g[tot++].nxt=head[u],g[tot].to=v,head[u]=tot;
}仔细想想，这样
tm还是同一条边吗？前面加了以后就和后面脱离了！！！正确写法应该是：
void add(int u,int v){
g[tot].nxt=head[u],g[tot].to=v,head[u]=tot++;
}或者直接把tot初始值为-1（较推荐），老老实实写这个：
void add(int u,int v){
g[++tot].nxt=head[u],g[tot].to=v,head[u]=tot;
}还是 按老样子写 好。。。
25.纸条
被上次的题迷惑了，明明这次只要判相邻两个不相同就行了，没必要全部丢进map里看。相邻两个就是前缀和后缀拼接起来，一旦有前缀不等了那么后面拼接成的矩阵就不可能和前面的就不会和前面相等了。
26.CF1442D
没常识，我用vector存数组值没有resize一下，导致RE了好久，resize的作用是申请数组大小，用动态数组不进行resize的话，里面是没有内存空间的，你访问就会越界，又不是pushback，pushback会在放入尾部的同时申请数组大小，但是你直接用下标访问没这个功能，会RE。
更智障的错误来了，递归到最后一层，你还跑个
O(n^2) ，最后一层有n 个数，那还不是n^3 的吗？？还有明明第0列被你用来存元素个数，你还把它当做物品进行背包。。。。
//RE代码（部分）
dp.clear();
for(int j=m;j>=0;j--)
dp[j]=max(dp[j],...);
//你会发现，用数组下标时，访问到未申请的空间会RE//正确写法（部分）
dp.resize(m+1);
//resize用法，就在里面直接写上申请空间大小
for(int j=m;j>=0;j--)
dp[j]=max(dp[j],...);
27.维护数列
写平衡树，线段树时别偷懒,这么写可能有问题，如下。
#define ls t[x].ch[0]
#define rs t[x].ch[1]别光写个ls上去，起码要写成ls(x)，比如这样，这么写是基本没问题的。
#define ls(x) t[x].ch[0]
#define rs(x) t[x].ch[1]另外，变量名写错祭，写平衡树merge后不更新rt祭
回收利用空间写假了，直接把原来的cnt节点数用p替换,结果忘改cnt++，变成了p++，空间不减反增。
//正确回收
int New(int x){
int y=max(x,0),p;p=(top==0)?(++cnt):(bac[top--]);
t[p].ch[0]=0,t[p].ch[1]=0;
t[p].pre=y,t[p].lst=y,t[p].mas=y,t[p].val=x;
t[p].siz=1,t[p].sum=x,t[p].rnd=rand();return p;
}
重新回收空间记得左右孩子清空，不然...你知道的，还有遍历一下所有点复杂度也就O(tot)，不影响时间（至于为什么看题）。
//删掉的时间问题不大
void del(int c){
if(!c) return ;bac[++top]=c;del(ls(c));del(rs(c));return ;
}用Treap进行区间最大值的维护时，注意如果在有负数的条件下，记得先判它的左右孩子为不为空，不然的话有可能维护的最大值会变为0（与t[0].mx比较，t[0]是空的，自然有几率会变成0）。
注意写成这样的分治
int solve(int l,int r){
if(l==r) return New(a[l]);int mid=(l+r)>>1;
return merge(solve(l,mid),solve(mid+1,r));
}它solve的调用顺序是先求solve(mid+1,r)再solve(l,mid)，但运算顺序仍然从左到右。
即merge中先求出solve(mid+1,r)再solve(l,mid)，但仍然左区间是solve(l,mid)，右区间是solve(mid+1,r)，这个我也不知道为什么，注意一下，所以这么写要一次性输入完，不然就反了。
28.排序机械臂
注意到它说的是与原序列相对位置相同，所以我们不能光靠找最小值来规避，因为它翻转后又会反一反。那么就离散化一步到位。
bool cmp(pp x,pp y){return x.val==y.val?(x.id<y.id):(x.val<y.val);}
for(int i=1;i<=n;i++) b[i].id=i,b[i].val=a[i];
sort(b+1,b+n+1,cmp);29.CF246E Blood Cousins Return
数组忘开两倍。
树状数组不能在第0位上add，会陷入死循环。
30.来自德温王的提醒，printf("%lld ",4713);这样输出会在CCF的评测机上RE掉，或输出乱七八糟的东西。还有for(int i= ;i<=(一个long long 类型的数);i++)也会出岔子。
31.CF715B
点和边的范围不一致，导致边数组开小，莫名TLE/RE。
没有仔细分析边权，跑单源最短路时可以爆long long
32.CF264B
答案长度最小为1，有些时候因为不能统计到特殊情况而会导致出错，使答案变小
33.CF13E
弹飞绵羊双倍经验题，我居然没看错题意，还是输出了一个不是答案的东西：题目要求的是最后一个跳出的，而不是跳进最后一个块的！！！
void renew(int x){
for(re int i=min(n,x*unit);i>=(x-1)*unit+1;--i){
int t=i-(x-1)*unit;
if(i+a[i]>n) pre[x][t]=-1,bon[x][t]=1,jump[x][t]=i;
else if(i+a[i]>x*unit) pre[x][t]=i+a[i],bon[x][t]=1,jump[x][t]=i+a[i];
else pre[x][t]=pre[x][t+a[i]],bon[x][t]=bon[x][t+a[i]]+1,jump[x][t]=jump[x][t+a[i]];
}
}
void query(int x){
int ans=0,pos=x;
while(x!=-1){
int t=x-(bl[x]-1)*unit;
if(pre[bl[x]][t]==-1) pos=jump[bl[x]][t];
ans+=bon[bl[x]][t];x=pre[bl[x]][t];
}
printf("%d %d\n",pos,ans);
}34.假期的宿舍
二分图匈牙利算法注意必须要判vis[v]==1就break掉，显然这陷入一个环，不能作为增广路。
int find(int u){
for(int i=head[u];i!=-1;i=g[i].nxt){
int v=g[i].to;
if(!vis[v]){
vis[v]=1; //这里
if(mac[v]==-1||find(mac[v])){
mac[v]=u;return 1;
}
}
}
return 0;
}题意要看清，题目中0是在校，1是不在校，与我们的潜意识相反。
还有多测，你在中途return 0是什么鬼？？？
35.证书/ P4556 [Vani有约会]雨天的尾巴 /【模板】线段树合并
线段树合并至少要开40~64倍数组，开少了直接RE，挂分严重，注意线段树合并的空间至少要开nlogn的，别像个憨憨似的白白送分。
const int N = 1e5+9;
struct segment{int l,r,siz,smx;}t[N<<6];
//大哥，请记住了线段树合并要有nlogn的空间大小，
//因为你不是给同一棵线段树上加点，而是不同的线段树!!!
//你每次操作会开logn的点，那么n此操作就要nlogn的空间。我想到了要判无救济粮的情况，但是在代码中很好的被忽略了。。。
void pushup(int c){
if(!t[c].l||!t[c].r){
t[c].siz=t[t[c].l].siz+t[t[c].r].siz;
t[c].smx=t[t[c].l].smx+t[t[c].r].smx;
return ;
}
if(t[t[c].l].siz>=t[t[c].r].siz)
t[c].siz=t[t[c].l].siz,t[c].smx=t[t[c].l].smx;
else t[c].siz=t[t[c].r].siz,t[c].smx=t[t[c].r].smx;
return ;
}
int merge(int x,int y,int l,int r){
if(!x||!y) return x+y;
if(l==r){
t[x].siz+=t[y].siz,t[x].smx=t[y].smx;
t[y].siz=0,t[y].smx=0;return x;
}
int mid=(l+r)>>1;
t[x].l=merge(t[x].l,t[y].l,l,mid);
t[x].r=merge(t[x].r,t[y].r,mid+1,r);
pushup(x);t[y].l=0,t[y].r=0,t[y].siz=0,t[y].smx=0;
return x;
}
//对于已有节点但是在做加法时siz减为0的点，你的合并是无法将它删掉的
void dfs2(int u,int fa){
for(int i=head[u];i!=-1;i=g[i].nxt){
int v=g[i].to;if(v==fa) continue;
dfs2(v,u);rt[u]=merge(rt[u],rt[v],1,cnt);
}
ans[u]=t[rt[u]].smx;
if(t[rt[u]].siz<=0) ans[u]=0;
//由于你pushup会直接忽略掉空节点，在删除加入过程中产生的空节点你是无法把它删掉。
//那么很有可能出现有标记，但就是siz=0的情况，特判一定要判掉（你既然都已经判siz<0了，=0怎么就没判判掉呢？）
}
36.雇员
你显然不能只加差分后的数组啊，你在dfs的过程中如果遇到无雇员的情况就return掉，但是你这位置很有可能不是从第一个dalao开始的啊。
void dfs(pp x,int &pos){
if(!x.j){pos=sum[x.i];return ;}
pp wt=pre[x.i][x.j][x.k];dfs(wt,pos);
if(x.i!=wt.i) pos+=p[x.i];
pos+=(x.j-wt.j);
// printf("%d %d %d %d\n",x.i,x.j,x.k,pos);
for(int i=pos-(x.j-wt.j)+1;i<=pos;i++) printf("%d ",i-1);
}37.矩阵游戏
38. CF894D Ralph And His Tour in Binary Country
又发现自己代码里隐藏的BUG了
#define ls(x) x<<1
#define rs(x) x<<1|1这么写在本题的数据下会溢出（CF的机子上），我也不知道为什么，改成这样就过了。
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)39.SP2916
莫名错误。。。
外面的变量名在里面重定义了一遍，导致没有实质更新ans
int al,ar,bl,br,ans=0;scanf("%d%d%d%d",&al,&ar,&bl,&br);
if(ar<bl){
ans=query(1,1,n,al,ar).rst+query(1,1,n,ar+1,bl-1).sum+query(1,1,n,bl,br).lst;
}
else{
int ans=-inf;//重新定义了遍，居然没RE，但是无法更新外面的
pp x=query(1,1,n,al,bl-1),y=query(1,1,n,bl,ar),z=query(1,1,n,ar+1,br);
pp ll=x+y,rr=y+z;
ans=max(y.mas,x.rst+y.sum+z.lst);
ans=max(ans,max(ll.rst+z.lst,x.rst+rr.lst));
}
printf("%d\n",ans);求最大子段和大部分题目要求不为空，所以用线段树实现的时候最好重载运算符。
线段树基本是你维护线段内某个东西，就很容易得到任意一个区间的这个东西，实现方式以重载运算符较为简单。
pp operator+(const pp x,const pp y){
pp z;z.sum=x.sum+y.sum;z.lst=max(x.lst,x.sum+y.lst);z.rst=max(y.rst,y.sum+x.rst);
//一开始我写成了z.lst=max(x.lst,x.sum+max(y.lst,0));
//但其实没必要因为x.lst>=x.sum，若y.lst<0，那么x.lst>x.sum+y.lst
z.mas=max(max(x.mas,y.mas),x.rst+y.lst);return z;
}
还有求最大子段和对于最大前缀和和最大后缀和的维护，是跟加的顺序有关的，所以不能那一个空的乱加，因为emp+x != x
//改正后的query
pp query(int c,int l,int r,int x,int y){
pp ans;ans.sum=0,ans.rst=0,ans.lst=0,ans.mas=0;
if(x>y) return ans;if(x<=l&&r<=y) return t[c];int mid=(l+r)>>1;
if(y<=mid) return query(ls(c),l,mid,x,y);
if(x>mid) return query(rs(c),mid+1,r,x,y);
return query(ls(c),l,mid,x,y)+query(rs(c),mid+1,r,x,y);
}平衡树又双叒叕写挂，这次错在一是漏加了个max(,0)，二是未特判孩子节点为空的情况（题目中，子段不为空），正确的update如下。
void update(int c){
t[c].siz=t[ls(c)].siz+t[rs(c)].siz+1;
t[c].sum=t[ls(c)].sum+t[rs(c)].sum+t[c].val;
if(ls(c)) t[c].lst=max(t[ls(c)].lst,t[ls(c)].sum+max(t[rs(c)].lst,0)+t[c].val);
else t[c].lst=t[c].val+max(t[rs(c)].lst,0);
if(rs(c)) t[c].rst=max(t[rs(c)].rst,t[rs(c)].sum+max(t[ls(c)].rst,0)+t[c].val);
else t[c].rst=t[c].val+max(t[ls(c)].rst,0);
bool flag=0;
if(ls(c)) t[c].mas=t[ls(c)].mas,flag=1;
if(rs(c)&&flag) t[c].mas=max(t[c].mas,t[rs(c)].mas);
if(rs(c)&&!flag) t[c].mas=t[rs(c)].mas,flag=1;
if(flag) t[c].mas=max(t[c].mas,max(t[ls(c)].rst,0)+max(t[rs(c)].lst,0)+t[c].val);
else t[c].mas=t[c].val;
return ;
}常见查平衡树错的方法：1.中序遍历后输出序列，看对不对。2.多测几组样例，看看输出会不会随srand中值改变而改变。
隔壁告诉我用重载运算符来简化update的步骤，并且在每个节点开一个bool数组判断是否为空节点，这样的话在重载时可以直接如果一个为空，return 另一个。
写树剖时没经脑子思考，把点dfs序重新标号写到第一个dfs上去了，应该实在dfs2中，因为到了dfs2才会对点根据轻重儿子重新标号。
注意重载运算符记得把结构体内所有元素都赋个初值，看下列代码，自己慢慢体会。
//没问题的
segment operator+(const segment x,const segment y){
segment z;z.tag=inf,z.len=x.len+y.len;
z.lst=0,z.mas=0,z.rst=0,z.sum=0;z.sum=x.sum+y.sum;
z.lst=max(x.lst,x.sum+y.lst);z.rst=max(y.rst,y.sum+x.rst);
z.mas=max(max(x.mas,y.mas),x.rst+y.lst);return z;
}
//有问题的
segment operator+(const segment x,const segment y){
segment z;//因为tag有初值1e9，且在这里申请一个结构体不保证里面所有东西初值为0
z.lst=0,z.mas=0,z.rst=0,z.sum=0;z.sum=x.sum+y.sum;
z.lst=max(x.lst,x.sum+y.lst);z.rst=max(y.rst,y.sum+x.rst);
z.mas=max(max(x.mas,y.mas),x.rst+y.lst);return z;
}40.TreeCutting
被卡常了，他们说的筛法好像也不太行，还是老老实实转成dfs序吧，不用递归，弹出的时候比较方便，事实上快了不少。
int dfs(int x){
for(int i=n;i>=1;i--){
int u=dfn[i];siz[u]=1;
for(int j=head[u];j!=-1;j=g[j].nxt){
int v=g[j].to;if(id[v]<id[u]) continue;
siz[u]+=siz[v];
}
if(siz[u]>x) return 0;
siz[u]%=x;
}
return (siz[dfn[1]]==0);
}
void Dfs(int u,int fa){
dfn[++num]=u,id[u]=num;
for(int i=head[u];i!=-1;i=g[i].nxt){
int v=g[i].to;if(v==fa) continue;
Dfs(v,u);
}
}41.Innopolis Open C.Optimal Truck
更加令人窒息的错误来了，一开始单个操作只要二分一下即可，然后由于多个询问，就想到了整体二分，
思路异常顺畅，要不是向隔壁确认了下，就真的去写整体二分了，其实只要对物品排个序，对询问排个序，双指针下即可（毕竟答案只有可能是某个物品的体积嘛）结果由于莫名的错误导致调了半天，看来考试时还是不能一直刚一道题而导致其它题失分。
42.Fairy
本来想奇环偶环分开来覆盖的，结果在奇环的时候把偶环也覆盖了，偶环的时候倒没覆盖，糊涂了。
//奇环偶环的覆盖写一块了，错误代码示范。
int p=lca(e[i].u,e[i].v);
int len=dep[e[i].u]+dep[e[i].v]-2*dep[p]+1;
if(len%2==1){
flag++;wc=i;
ji[e[i].u]+=1,ji[e[i].v]+=1,ji[p]-=2;
ou[e[i].u]+=1,ou[e[i].v]+=1,ou[p]-=2。
//奇环的时候却把偶环也覆盖了，晕倒
}
43.测试程序
注意：对所有题面内未注明为正数的变量，思考该变量取值为0对答案有什么影响。（同CSP2020函数调用）
人生第一次印象深刻地被卡精度，虽然也说不好是不是我的错，但是以后要注意强制类型转换的顺序，最好直接加个(double) (long long) 。
44.Bouncing Ball
首先没看清题目要求至少剩下 p 个。
第二点是没弄清 p 和 k 的大小关系，如果 p 比 k 大，那么 p%k<k，所以有可能被重复统计到（在第一次写的时候）
第三点是多测数组不用memset清空的后遗症，扫一遍数组清空固然没问题，但是请注意，你清空的时候必须把 将要访问到的数组上界 都清空。
在本题，虽然不用访问到超过 n 以外的数组下标，但是你在实现的时候不注意细节，没有特判访问越界的情况，导致越界后答案就不准了（具体看代码）。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5+9;
int T,n,p,k;ll a,b,f[N];
char s[N];
int main(){
scanf("%d",&T);
while(T--){
scanf("%d%d%d",&n,&p,&k);scanf("%s",s+1);
scanf("%lld%lld",&a,&b);
1.memset(f,0,sizeof(f));//正确的写法
2.for(int i=0;i<=n+10;i++) f[i]=0;//令人智熄的写法，它i+k显然可以大于n+10的啊。
for(int i=n;i>=1;i--){
if(s[i]=='0') f[i]=a;
1.f[i]+=f[i+k];//越界的原因，没判掉i+k>n，但是因为空间开的足够大，没RE，但是沿用了上一组数据的答案
2.if(i+k<=n) f[i]+=f[i+k];//最合适的写法
}
ll ans=-1;
for(int i=n;i>=1;i--){
int pos=i-p+1;if(pos<1) break;
ll area=1ll*(pos-1)*b+f[i];
if(ans==-1) ans=area;
else ans=min(area,ans);
}
printf("%lld\n",ans);
}
return 0;
}
45.XOR-gun
什么假算法一大堆的话就不说了，讲下在调正解的时候一些小细节出的锅。
for(int i=1;i<=n;i++){
int t=mp[p[i].val^1][p[i].pre];
if(t&&t<=cnt[p[i].val])
area=Min(area,i-t-1);
if(p[i].val) cnt[1]=i;
else cnt[0]=i;
for(int i=0;i<vec[p[i].val^1].size();i++){
//显然你变量重名了，调了半天也没调出来，显然它会弄出一大堆乱七八糟的东西。
//fxz耐心的跟我讲，变量重名的时候局部优先，所以这里vec[p[i].val^1].size()里的i会变成里面这个for循环的i，发生错误
pi tmp=vec[p[i].val^1][i];
mp[p[i].val^1][tmp.first]=tmp.second;
}
vec[p[i].val^1].clear();
vec[p[i].val].push_back(mcp(p[i].pre,i+1));
}46.风神之诗
这题的毒瘤卡常就不说了，讲下这里为什么我tarjan求lca写挂。
//正确代码
void dfs(int u,int fa){
dep[u]=dep[fa]+1,f[u]=u;//细节f[u]=u;
for(int i=head[u];i!=-1;i=g[i].nxt){
int v=g[i].to;if(v==fa) continue;
dfs(v,u);f[v]=u;
}
for(int i=head_quest[u];i!=-1;i=g[i].nxt){
int it=g[i].to;int v=(q[it].l==u?q[it].r:q[it].l);
if(f[v]&&!q[it].tag){
int lca=find(v);q[it].tag=1;int dis=dep[q[it].l]-dep[lca];
if(lca==q[it].r) dis+=1;
(ans+=(1ll*dis*q[it].id%mod))%=mod;
}
}
}下面是错误代码
void dfs(int u,int fa){
dep[u]=dep[fa]+1;
for(int i=head[u];i!=-1;i=g[i].nxt){
int v=g[i].to;if(v==fa) continue;
f[v]=[v];dfs(v,u);f[v]=u;
//细节f[v]=v;
}
for(int i=head_quest[u];i!=-1;i=g[i].nxt){
int it=g[i].to;int v=(q[it].l==u?q[it].r:q[it].l);
if(f[v]&&!q[it].tag){
int lca=find(v);q[it].tag=1;int dis=dep[q[it].l]-dep[lca];
if(lca==q[it].r) dis+=1;
(ans+=(1ll*dis*q[it].id%mod))%=mod;
}
}
}上面两份代码就只有细节这一处差别，但是就是有对错之分。我百思不得其解，最后发现他们的唯一区别在于根节点。
正确代码处理到了根节点，而错误代码没有，这会导致当lca为根节点1时求解错误。注意这个细节!
47.赛前临时回忆，如果用dev疯狂ctrl+Z，可能会出现代码错位的现象。
48.蹦蹦炸弹
错误点在于倍增数组定义时将指数放在第二维，使用的时候却在第一维访问指数，直接数组越界，最主要的是小数据看不出来。
int n,m,f[N][21];//注意到了吗，这里应该改为f[21][N]，注意自己数组下标的前后顺序，不要再犯这种低级错误。
//main函数中
for(int j=0;j<=20;j++) for(int i=1;i<=n;i++) f[j][i]=i;49.atcoder ARC contest 109.B
二分上界写错了，因为1+2+3+...+x=x
\ast (x+1)/2在最大数据下要<=1e18，然后忘记了除以2这个操作，把二分上界写成了1e9，实际上是2e9。因为x\ast (x+1)/2<=1e18，即x\ast (x+1)<=2e18，比1e9不知道大到哪里去了。
50.SP1553 BACKUP - Backup Files
吐了，多测不清空，怎么可能对！！！！更令我震惊的是链表不清空也会导致错（尽管链表需要每次for一遍，但是不清空它就是炸了）。
还有一个问题，就是上面判了堆为不为空，下面就忘判了。。结果它就Runtime Error了。
while(!q.empty()&&m){
while(!q.empty()&&vis[q.top().id]) q.pop();
if(q.empty()) break;//下面没判堆是否为空，为空的原因是上面弹的时候直接弹空了整个堆
int u=q.top().id;ans+=q.top().wt;q.pop();
val[u]=val[l[u]]+val[r[u]]-val[u];
q.push(node{u,val[u]});
vis[l[u]]=1,vis[r[u]]=1;del(l[u]);del(r[u]);
m--;
}51.成绩排名
啊这，推结论的时候想的很明白，结果写的时候就炸了。
void solve2(int x){
int l=x,r=len,Ans=x;
while(l<=r){
int mid=(l+r)>>1;
if(p[x]*t>=p[mid]) l=mid+1,Ans=mid;
else r=mid-1;
}
int num=sum[Ans]-sum[x]+1;
//错误写法：int num=sum[Ans]-sum[x-1];原因是当前排名为x的不一定要翻倍
(ans[x]+=C(m-num,n-num))%=mod;return ;
}在求第
i 个人的答案时，在第i 个人成绩翻倍的情况下，与第i 个人成绩相同的人得到翻倍并不会影响第i 个人的排名，所以他们不是必须要翻倍的人，不能计算在num里面，num表示为了使排名不变必须翻倍的人的个数。
52.树上染色
啊哈，现在树剖能打了，线段树调不出来了。。。。
修改权值的时候虽然二进制位变了（假设变为1），modify里的sum1++了，但是忘记了将原来二进制位为0的影响消去，即sum0忘记减减了（或最底层的sum0忘记从1变0了，还有那个d=-1的时候，如果不清空，相当于没操作）。
void modify(int &c,int l,int r,int x,int d){
if(!c) c=New();
if(l==r){
if(d==0) t[c].sm0=1,t[c].sm1=0;
if(d==1) t[c].sm1=1,t[c].sm0=0;
if(d==-1){s[++tp]=c;c=0;}
return ;
}
int mid=(l+r)>>1;if(x<=mid) modify(t[c].l,l,mid,x,d);if(x>mid) modify(t[c].r,mid+1,r,x,d);
pushup(c);
return ;
}53.剪辣椒
忘记了重心的性质：
1.重心一定在重链上
2.从某个节点出发进入一条轻边，子树大小至少除以二
一下子脑子卡壳了，割掉一个子树后就是找剩下树的重心，或者就是在重链上找siz是两倍自己的祖先（反正就是要使其中两个尽量相等），结果我忽略了找祖先上两倍siz的情况。
set挺好用的，其中找近似只要分别upper和lower一下就可以了（仅仅是移动指针的话还是好写的）。
#define si set<int >::iterator
#define mi multiset<int >::iterator
set<int >s;
multiset<int >s2;
int ans;
void dfs3(int u,int fa){
if(s.empty()) return ;
si p=s.lower_bound((n-siz[u])/2);
if(p==s.end()) --p;si t=p;
for(int i=0;i<=2;i++){
int x=(*t);
int mx=max(siz[u],max(x,n-x-siz[u]));
int mn=min(siz[u],min(x,n-x-siz[u]));
ans=min(ans,mx-mn);
if(t==s.begin()) break;t--;
}
t=p;
for(int i=1;i<=2;i++){
t++;if(t==s.end()) break;
int x=(*t);
int mx=max(siz[u],max(x,n-x-siz[u]));
int mn=min(siz[u],min(x,n-x-siz[u]));
ans=min(ans,mx-mn);
}
mi e=s2.lower_bound(siz[u]*2);
if(e!=s2.end()){
int x=(*e);
int mx=max(siz[u],max(x-siz[u],n-x));
int mn=min(siz[u],min(x-siz[u],n-x));
ans=min(ans,mx-mn);
}
e=s2.upper_bound(siz[u]*2);
if(e!=s2.end()){
int x=(*e);
int mx=max(siz[u],max(x-siz[u],n-x));
int mn=min(siz[u],min(x-siz[u],n-x));
ans=min(ans,mx-mn);
}
s2.insert(siz[u]);
for(int i=head[u];i!=-1;i=g[i].nxt){
int v=g[i].to;if(v==fa) continue;dfs3(v,u);
}
s2.erase(s2.find(siz[u]));
}54.path
花了一个晚上来证明zjj的错误代码。。。直接说吧，由k个点不断拓展的做法来求一个点集内最近点对是错的，原因跟最小生成树上为什么不是最短路径一样。
错误代码如下（能AC因为是在最后瞎搞了一波）：
while(!q.empty()){
while(!q.empty()&&(q.top().fr==a||q.top().fr==b)) q.pop();
if(q.empty()) break;
node x=q.top();q.pop();int u=x.id;
if(!vis[u]){
for(int i=head[u];i!=-1;i=g[i].nxt){
int v=g[i].to;
if(vis[v]!=x.fr) q.push(node{x.dt+g[i].val,x.fr,v});
}
vis[u]=x.fr;dis[u]=x.dt;
}
else{
if(vis[u]==x.fr) continue;
w1[++cut]=vis[u],w2[cut]=x.fr,w3[cut]=dis[u]+x.dt;
if(cut>40) break;
}
}
55.set
嘴上说着要与每条加边并入并查集的时间，结果就没判。。。
node path(int x){
node e;e=tag[x];int id=e.tm;
while(b.f[x]!=x){
id=max(id,b.tm[x]);x=b.f[x];if(tag[x].tm>id) e=tag[x],id=max(id,tag[x].tm);
}
return e;
}56.Quarrel(争吵)
真是恶习难改啊，没想到堆优化spfa与堆优化dij的小差别就导致Wa的惨剧。
先看代码，cnt表示最短路计数。
void dij(int u){
memset(vis,0,sizeof(vis));
memset(cnt,0,sizeof(cnt));
memset(dis,-1,sizeof(dis));dis[u]=0;
q.push(make_pair(0,u));cnt[u]=1;
while(!q.empty()){
int u=q.top().second;q.pop();
if(vis[u]) continue;vis[u]=1;
//堆优化dij和堆优化spfa就上面这一句话的区别
for(int i=head[u];i!=-1;i=g[i].nxt){
int v=g[i].to;
if(dis[v]==-1||dis[v]>dis[u]+g[i].val){
dis[v]=dis[u]+g[i].val,cnt[v]=cnt[u];
q.push(make_pair(-dis[v],v));
}
else if(dis[v]==dis[u]+g[i].val) (cnt[v]+=cnt[u])%=mod;
}
}
}就是没有'if(vis[u]) continue;vis[u]=1;'这一句话，导致没能Ac，因为这样会导致最短路计数出错。
你会发现u会从堆中被取出多次，也就是说，我们的'if(dis[v]==dis[u]+g[i].val) (cnt[v]+=cnt[u])%=mod;'会更新cnt[v]多次，这样就导致计数重复，出错。
有一个注意点：当两人相遇时，在端点相遇和在道路上相遇的情况是不同的，因为在端点时，只强制经过一个点，而在道路上时，需要强制经过这条道路，所以方案数不同。
57.[SDOI2004]LIS
Ctrl+Z按久了，不小心把正确的代码给撤销掉了，导致多组数据时输出只输出了一组。别把单组数据的输出放在while(T--)外面!!!
58.CF1172B Nauuo and Circle
真的是呃呃呃，本来一道大水题，，思路也是对的，结果式子列错了，却还过了样例???
本来就是
n+1 个数随便排列(n+1)! 的事，结果我非要按从n 个数中选择x 个放我前面，n-x 放我后面，就挂了，原因是这样的：我列的式子
C_n^x\times x!\times C_n^{n-x}\times (n-x)! ，但实际上那n-x 个点是确定的，就是去掉那x 个数剩下来的数，所以正确的式子应该是C_n^x\times x!\times (n-x)! ，总共(n+1) 个这个东西相加，故与(n+1)! 等价，即n+1 个数随便排列。
void dfs(int u,int fa){
int son=0;f[u]=1;
for(int i=head[u];i!=-1;i=g[i].nxt){
int v=g[i].to;if(v==fa) continue;
dfs(v,u);son++;(f[u]*=f[v])%=mod;
}
if(u!=1) son++;
(f[u]*=fac[son])%=mod;
return ;
}59.[HAOI2011]problem a
第一次知道结构体用map的话要重载小于号，自定义运算符。
struct pp{int l,r,val;}p[N],c[N];
bool operator<(const pp x,const pp y){
return x.l==y.l?(x.r<y.r):(x.l<y.l);
}
map<pp ,int >mp;写题的时候糊涂了，就把p和c这两个变量名写重了。。。
sort(p+1,p+cnt+1,cmp);//应该是c的，都写成了p
int j=0;
for(int i=1;i<=n;i++){
while(j<cnt&&p[j+1].r<=i){//应该是c的，都写成了p
j++;
f[i]=max(f[i],f[p[j].l-1]+p[j].val);//应该是c的，都写成了p
}
f[i]=max(f[i],f[i-1]);
}60.[NOIP2020]排水系统
其实并不用写高精，盲猜数据中只有分母会爆unsigned long long，并且能爆unsigned long long 的只有
60^{11} ，其它都爆不了，所以只要特判一下分母有没有爆溢出即可。怎么判有没有溢出，很简单，假设需要判断
a\ast b 有没有溢出，只要拿这个类型中的最大数除以a 与b 比大小就可以了。至于怎么求 unsigned long long 下的最大数，只要在 unsigned long long 下定义一个为
-1 的数就可以了，因为它可以溢回去神奇吧
ll td=-1;
for(int i=1;i<=n;i++)
if(!ot[i]){
if(e[i]==0){
printf("0 1\n");
continue;
}
ll p=wh;
ll x=gcd(e[i],p);e[i]/=x,p/=x;
x=gcd(e[i],w[i]);e[i]/=x,w[i]/=x;
if(w[i]>td/p) printf("%lld 36279705600000000000\n",e[i]);
else printf("%llu %llu\n",e[i],w[i]*p);
}61.count on a tree
树上莫队的典型代表题，说到底还是在序列上莫队，转为欧拉序（每个点算进来和出去共两次，序列长度为2n）。第一个注意点是如果u,v不是祖先关系，他们的lca在欧拉序上一定会漏考虑其贡献，单独特判。
第二点是一个点在莫队维护的区间中，如果出现了两次那么相当于这个点不在查询的路径上，单独开个数组维护每个点在序列上是否存在（每次异或个1即可）。
第三点就是不要把颜色和一个点是否出现混为一谈，要分开两个数组维护，因为可能多个点对应同一颜色，一个点出现了两次离开了当前的路径并不意味着这条路径上没有这个颜色。
int c[N],ans,w[N];
void M(int x,int d){
w[dfn[x]]^=1;
if(!w[dfn[x]]) c[a[dfn[x]]]--;
else c[a[dfn[x]]]++;
if(c[a[dfn[x]]]==1&&w[dfn[x]]) ans+=1;
if(c[a[dfn[x]]]==0&&!w[dfn[x]]) ans-=1;
return ;
}62.【模板】回滚莫队
真的是
人太菜了啥错误都有。。。1.回滚莫队的 L,R 交替的时候写成 for(int L=1,R=1;L<=m;R=L+1)，那你交替了个寂寞。。。是L=R+1;
2.多次min/max复杂度太大。
3.先看以下代码。。。
for(;L<=R;L++){
if(bl[q[L].l]!=bl[q[L].l]) break;
//这不废话嘛，你break了个寂寞，啥都没break掉，还大常数的跑了那么久。
//应该是bl[q[L].l]!=bl[q[L].r] break;
ans=0;int tot=0;
for(int i=q[L].l;i<=q[L].r;i++){
if(mn[a[i]]==inf) mn[a[i]]=i,cl[++tot]=a[i];
ans=max(ans,i-mn[a[i]]);
}
for(int i=1;i<=tot;i++) mn[cl[i]]=inf;
Ans[q[L].id]=ans;
}正确代码如下：
for(int L=1,R=1;L<=m;L=R+1){
while(R<m&&bl[q[L].l]==bl[q[R+1].l]) R++;
for(int i=1;i<=len;i++) mn[i]=inf,mx[i]=0;
for(;L<=R;L++){
if(bl[q[L].l]!=bl[q[L].r]) break;
ans=0;int tot=0;
for(int i=q[L].l;i<=q[L].r;i++){
if(mn[a[i]]==inf) mn[a[i]]=i,cl[++tot]=a[i];
ans=max(ans,i-mn[a[i]]);
}
for(int i=1;i<=tot;i++) mn[cl[i]]=inf;
Ans[q[L].id]=ans;
}
ans=0;
int l=bl[q[L].l]*unit;int r=l+1,st=l;
M(l);M(r);
for(int i=L;i<=R;i++){
while(r<q[i].r) M(++r);
int tmp=ans;
for(int j=q[i].l;j<=st;j++) cn[a[j]]=mn[a[j]],cx[a[j]]=mx[a[j]];
while(l>q[i].l) M(--l);
Ans[q[i].id]=ans;ans=tmp;
for(int j=q[i].l;j<=st;j++) mn[a[j]]=cn[a[j]],mx[a[j]]=cx[a[j]];
ans=tmp;
l=st;
}
}63.[Ynoi2019模拟赛]Yuno loves sqrt technology II
不好意思，数组越界，少了 80 分，呃。。。
void pushup2(int x){
// printf("bl:");
for(int i=bl[x];i<=bl[len];i++) b[i]++/*,printf("%d ",i)*/;//puts("");
// printf("num:");
int ed=bl[x]*unit;//应该与n取min的，不然就会UB了
for(int i=x;i<=ed;i++) f[i]+=1/*,printf("%d ",i)*/;//puts("");
return ;
}64.[TJOI2015]弦论
void solve(int l,int r,int h){
if(l>r) return ;
if(l==r){
if(p<=n-sa[l]+1-h){
for(int i=sa[l];i<=sa[l]+h-1+p;i++) printf("%c",s[i]);puts("");
exit(0);
}
p-=(n-sa[l]+1-h);
return ;
}
int ps=rmq(l+1,r);
int len=(ht[ps]-h)*(r-l+1);
if(p<=len){
for(int i=sa[ps];i<=sa[ps]+h-1;i++) printf("%c",s[i]);
for(int i=sa[ps]+h;i<=n;i++){
p-=(r-l+1);printf("%c",s[i]);
if(p<=0) break;
}
exit(0);
}
p-=len;
solve(l,ps-1,ht[ps]);solve(ps,r,ht[ps]);
return ;
}
像我这样厚颜无耻之徒肯定会把错误原因归为不会证复杂度的反正我自己胡的单调栈的做法假了，因为有可能是后面的管到前面，不细说。还是来讲下自己为什么在正解面前犹豫不决。
还是复杂度的问题，原本我胡出来的把区间分为两半的做法是对的，只不过不能严谨分析复杂度而没敢写，现在算是能分析上面那个代码的复杂度了。
复杂度分析：上面的那份代码是将
[1,n] 的区间一刀切开，分为两半（但不一定是取中点切），切开的复杂度为O(1) ，试证明这样做的复杂度是线性，且区间个数最多为4n 个。证明如下，考虑一个数左右两边分别都只有一次机会来作为切割位置，所以总的切割数
\leq2n 。又因为一刀切带来的是两个区间，所以区间个数总共为4n 个。证明这个的目的是想以后遇到相似体型的时候就直接干，只要区间处理的复杂度为
\log n 或O(1) 即可。
65.[SDOI2011]染色
两个憨批错误。一个是如果两边和中间的颜色都相同，那么颜色块数要减1。二是，注意 LCT 维护的东西只要可能变动就要重新赋值。
细品以下细节造成的误差
void pushup(int x){
//......错误代码中部分的致命细节
if(ls(x)) t[x].lc=t[ls(x)].lc;
if(rs(x)) t[x].rc=t[rs(x)].rc;
//......仔细看
}看出来了吗？如果有左孩子，就要取左孩子右边的颜色，但是如果没有左孩子，就要把颜色赋为自己的颜色
Q:自己的颜色不是一开始就赋上去了吗？
A:Too young too simple,I'm so naive.注意，因为LCT维护的过程中，可能早已把 t[x].lc 改成非自己的颜色，然后你把旁边的边都变为虚边后（makeroot或者其它函数时），它左右两边可能没有子节点，而它本身的lc和rc（left_color和right_color的缩写）已经被改成其他颜色了，这时候如果不改回来那么维护的信息就肯定错了。
void pushup(int x){
t[x].sum=t[ls(x)].sum+t[rs(x)].sum+1;
if(ls(x)) t[x].lc=t[ls(x)].lc;else t[x].lc=t[x].col;
if(rs(x)) t[x].rc=t[rs(x)].rc;else t[x].rc=t[x].col;
if(ls(x)&&rs(x)) t[x].sum-=((t[x].col==t[ls(x)].rc)+(t[x].col==t[rs(x)].lc));
else if(ls(x)) t[x].sum-=(t[x].col==t[ls(x)].rc);
else if(rs(x)) t[x].sum-=(t[x].col==t[rs(x)].lc);
else t[x].sum=1;return ;
}66.[AHOI2005]航线安排
错误代码如下，其目的为dfs一棵splay上的所有节点，并把它们揉成一个节点（LCT维护边双的模板题）
void dfs(int x){
if(!x) return ;
pushdown(x);
merge(ls(x),x),dfs(ls(x));
merge(rs(x),x),dfs(rs(x));
return ;
}正确代码如下，体会这细微的差别
void dfs(int x){
pushdown(x);
if(ls(x)) merge(ls(x),x),dfs(ls(x));
if(rs(x)) merge(rs(x),x),dfs(rs(x));
return ;
}你会发现，区别仅在于一个与0并查集merge了一下，另一个不会与0 merge，（虽然在开头判了，但仍然防不住上一层就将为0的ls(x)与x合并merge了一下）
与0合并的正确性显然会出错，因为会把两个不相干的东西揉在一起，甚至会出现段错误，因为这么做有可能是某个节点x的t[x].fa==x，这样的话就会不停上跳，无法遇到空的父亲节点而停止，形成死循环
还有注意下，将一棵splay揉成一个点后，需要将这个新的节点左右孩子都清空，因为无法保证这个节点在原splay上就没有左右孩子
void Ease(int x,int y){
split(x,y);dfs(y);x=ff(y);
t[x].siz=1,t[x].tag=0,t[x].fa=t[y].fa;
t[x].ch[0]=0,t[x].ch[1]=0;
return ;
}67.最小差值生成树
我真的是醉了，LCT没写炸，反而主函数的东西写挂了，错误代码如下
int main(){
scanf("%d%d",&n,&m);int num=n;
for(int i=1;i<=n;i++) a[i]=inf;
for(int i=1;i<=m;i++){
++num;int u,v;scanf("%d%d%d",&u,&v,&a[num]);
e[i].id=num,e[i].u=u,e[i].v=v;
}
for(int i=1;i<=num;i++) t[i].val=a[i],t[i].ps=i;
for(int i=1;i<=num;i++) f[i]=i,sz[i]=1;
sort(e+1,e+m+1,cmp);int ans=inf;
for(int i=1;i<=m;i++){
int u=e[i].u,v=e[i].v;
if(u==v) continue;
if(findroot(u)!=findroot(v)){
link(u,e[i].id);link(v,e[i].id);merge(u,v);
s.insert(a[e[i].id]);
if(sz[find(1)]==n){
mi ed=s.end();--ed;mi ac=s.begin();
ans=min(ans,(*ed)-(*ac));
}
continue;
}
split(u,v);int ps=t[v].ps;
if(ps>n){
cut(ps,e[ps-n].u);
cut(ps,e[ps-n].v);
//错误所在，不是ps-n，因为现在的e已经排过序了
s.erase(s.find(a[ps]));
}
link(u,e[i].id);link(v,e[i].id);
s.insert(a[e[i].id]);
if(sz[find(1)]==n){
mi ed=s.end();--ed;mi ac=s.begin();
ans=min(ans,(*ed)-(*ac));
}
}
printf("%d\n",ans);
return 0;
}你会发现，在上面的错误代码中误把 ps 对应的边对应为 ps-n。没错，在刚输进来的时候的确是 id 和 id-n 的关系，但是你的 e 数组可是排过序的啊!!!!（即不是刚输进来的顺序）
因此 ps 对应的边在所有边排序后大概率不可能在原来的位置，按照 ps-n 来的话，显然会割掉一条本来就不存在的边，容易导致 RE 的情况。
int main(){
scanf("%d%d",&n,&m);int num=n;
for(int i=1;i<=n;i++) a[i]=inf;
for(int i=1;i<=m;i++){
++num;int u,v;scanf("%d%d%d",&u,&v,&a[num]);
e[i].id=num,e[i].u=u,e[i].v=v;
}
for(int i=1;i<=num;i++) t[i].val=a[i],t[i].ps=i;
for(int i=1;i<=num;i++) f[i]=i,sz[i]=1;
sort(e+1,e+m+1,cmp);int ans=inf;
for(int i=1;i<=m;i++) ys[e[i].id]=i;
for(int i=1;i<=m;i++){
int u=e[i].u,v=e[i].v;
if(u==v) continue;
if(findroot(u)!=findroot(v)){
link(u,e[i].id);link(v,e[i].id);merge(u,v);
s.insert(a[e[i].id]);
if(sz[find(1)]==n){
mi ed=s.end();--ed;mi ac=s.begin();
ans=min(ans,(*ed)-(*ac));
}
continue;
}
split(u,v);int ps=t[v].ps;
if(ps>n){
cut(ps,e[ys[ps]].u);
cut(ps,e[ys[ps]].v);
s.erase(s.find(a[ps]));
}
link(u,e[i].id);link(v,e[i].id);
s.insert(a[e[i].id]);
if(sz[find(1)]==n){
mi ed=s.end();--ed;mi ac=s.begin();
ans=min(ans,(*ed)-(*ac));
}
}
printf("%d\n",ans);
return 0;
}68.[NOI2014]魔法森林
错误代码片段1
if(e[t[v].mx-n].b>e[i].b){
cut(t[v].mx,e[t[v].mx-n].u);
cut(t[v].mx,e[t[v].mx-n].v);
link(u,n+i);link(v,n+i);
}
注意下，第一遍cut后,t[v].mx会发生改变，因为LCT在cut的时候会把t[v].mx更新掉，导致接下来cut掉的边不是我们想要的那一条，所以需要提前记录下t[v].mx，不然的话就很可能会导致报错
错误代码片段2
//错误代码
void pushup(int x){t[x].mx=Max(x,Max(ls(x),rs(x)));return ;}
//正确代码
void pushup(int x){t[x].mx=Max(x,Max(t[ls(x)].mx,t[rs(x)].mx));return ;}这维护了个鬼头!?拜托，和x比较的不应该只是ls(x)，rs(x)，而应该是ls(x)和rs(x)所代表的所有节点的最大值!
69.九条可怜与不用推的式子
首先注意数组不要越界
poly operator*(poly x,poly y){
poly z;
for(int i=0;i<=k;i++) z.f[i]=0;
for(int i=0;i<x.deg;i++)
for(int j=0;j<y.deg;j++){
if(i+j>k) break;
(z.f[i+j]+=x.f[i]*y.f[j]%mod)%=mod;
}
z.deg=min(x.deg+y.deg,k+1);//不取min，则数组要开两倍，防止越界
while(z.deg&&!z.f[z.deg-1]) z.deg--;
return z;
}两个多项式相乘，次数会达到两倍，虽然要限制在k以内，但是在细节处比如说更新度时需要取min，或干脆直接开两倍数组
第二点则是个显而易见的小心得，就是如果我们只需要模
x^n 意义下的多项式，可以直接把次数大于等于n 的丢弃，并不会影响它的四则运算，因为即使变成两个新的多项式相乘，但是这两个新的多项式相乘在模意义下与原来的多项式相乘的结果等价，所以我们就可以“抛弃”原来的式子了，只需要考虑新多项式相乘在模意义下的结果
70.第二类斯特林数·行
for(n=1;n<=(m+1);n<<=1);//错误代码
for(n=1;n<=2*(m+1);n<<=1);//正确代码注意，两个长度为
m 的多项式相乘得到一个2m 长度的多项式，如果只开m+1 位，则只能保证后m+1 位结果正确（别问我怎么知道的，可能不准确，以后还是老老实实开两倍长度吧，太危险了，分治FFT也开个两倍吧，尽管它是正确的）
71.最大XOR路径
空间开大一倍就过去了
但检查下数据范围发现自己没挂，最后发现的原因是找部分环的时候环的个数大于 N 了，所以空间要开大一倍
提醒我们不能只看输入数据的范围，代码实现的时候的过程量的大小也是要注意的
72.[NOI2008] 志愿者招募
犯网络流的大错啦，因为正向边和反向边要求异或
1 的关系，所以 tot 要从 -1 开始，这一点和普通的图论不太一样
memset(head,-1,sizeof(head));tot=-1;//正确代码
memset(head,-1,sizeof(head));tot=0;//错误代码73.树上 k 级祖先
n,m搞混，输出错误，以为 n,m 同阶，数组开小了
74.CF938G Shortest Path Queries
合并两个并查集的时候拿的是到根的异或路径长度而非到它父亲的异或路径长度
75.无限之环
上面的数组开了
4 倍，下面就忘开了
76.Gym（后面的数字我忘了）
忘记在传值的时候开 long long ，调了老久
77.消息传递
访问 vector... t 的时候访问到了数组下标
t.size() ，但是它没有 RE ，因为 vector 实际开的数组在清空后并不会消失，在清空后下一次使用时会沿用上一次的数组，所以你访问越界不一定能返回段错误甚至会返回非零的值，导致答案错误就错了这个点吧，调了一下午
78.积木小赛
总的字符串个数为
2e5\ast 2e5 ，如果你哈希的话，单哈模数小于1e9 显然会被卡，必须要双哈才能过map 速度太慢，显然要手写哈希表，就是在双哈（本题需要）的前提下对于相同余数的写个邻接表，暴力查询就可以了
const ll MOD = 19260817;
int head[MOD],tot;
struct pp{int nxt;ll to;}g[N*N];
void add(ll u,ll v){
g[++tot].nxt=head[u],g[tot].to=v,head[u]=tot;
}
void insert(ll x){
ll u=x%MOD;
for(int i=head[u];i!=-1;i=g[i].nxt){
ll v=g[i].to;if(v==x) return ;
}
add(u,x);ans++;return ;
}79.CF1483F Exam
struct Count{
int ct[N],cl[N],tot;
void clr(){for(int i=1;i<=tot;i++) ct[cl[i]]=0;tot=0;return ;}
void add(int x){ct[x]++;cl[++tot]=x;return ;}
int query(int x){return ct[x];}
}cnt;
struct treearray{
int tr[N],V,cl[N],tot;
void clr(){for(int i=1;i<=tot;i++) tr[cl[i]]=0;tot=0;return ;}
int lowbit(int x){return x&(-x);}
void add(int x,int d){while(x<=V){tr[x]+=d,cl[++tot]=x;x+=lowbit(x);}return ;}
int sum(int x){int ans=0;while(x){ans+=tr[x];x-=lowbit(x);}return ans;}
}t;注意，不要以这样的方式 clr 来清空数组，尤其是树状数组，因为它理论上有
n\log n 的修改，数字大小上界为n\log n ，而一般题目树状数组用到时会到 1e6 这个级别， clr 数组开不下，很容易就直接 RE 掉。比较保险的清空方式如下（因为正着扫过去时间复杂度不会炸，那么我们再扫一遍把修改的地方改回来也不会炸）
for(int i=0;i<a.length();i++){
u=ACAM::t[u].ch[a[i]-'a'];
if(i==a.length()-1){
int p=cv[ACAM::t[u].fail];
if(p&&cnt.query(p)==t.sum(id[p]+sz[p]-1)-t.sum(id[p]-1)) ans++;
cnt.ct[p]=0;
}
else if(cv[u]){
if(cnt.query(cv[u])==t.sum(id[cv[u]]+sz[cv[u]]-1)-t.sum(id[cv[u]]-1)) ans++;
cnt.ct[cv[u]]=0;
}
}
u=0;for(int i=0;i<a.length();++i) {u=ACAM::t[u].ch[a[i]-'a'];t.add(id[u],-1);}
//这样很保险重新扫一遍是不会出问题的，对于分块，莫队之类的题也是成立的（保险确定）80.直线
能写平面向量的就别写解析几何了，容易炸精，还要特判
判平行就用叉积，判垂直就用点积好了
81.完美串
for(int i=0;i<=(n<<1);i++) sum[i]=sum[i-1]+a[i];这我还能说啥，访问越界本地还不 RE ，看来以后还要查一查数组是否越界，是否溢出，是否访问到了 -1
本地数组访问到 -1 都不报错，这就很阴间了啊啊
82.[IOI2018] werewolf 狼人
把题意看反还过了所有样例，我.....
注意这种绕来绕去的题意搞清楚是哪段要大于
L ，哪段要小于R 既然你在图上新开了其它点，那么就注意操作的时候不要再使用原来的
n 比如说SAM树/Kruskal重构树上倍增时节点数不再是
n ，而是cnt ，不要写错（而且小数据拍不出来，需眼查）
for(int j=1;j<=20;j++) for(int i=1;i<=cnt;i++) f[i][j]=f[f[i][j-1]][j-1];
//cnt别写错，写成n就坏了83.AT4168 [ARC100C] Or Plus Max
高维前缀和你既可以写成这样
for(int i=0;i<n;i++)
for(int j=0;j<(1<<n);j++)
if(j&(1<<i)) f[j]+=f[j^(1<<i)];也可以写成这样
for(int j=0;j<(1<<n);j++)
for(int i=0;i<n;i++)
if(j&(1<<i)) f[j]+=f[j^(1<<i)];但类似背包，如果你按第一种写法，会有一个好处可以求
i,j 满足i 和j 至少有一位不同的max(a_i+a_j) ，说白了就是i!=j 思路就是原本第
k 位为0 的可以更新为1 的，这样可以防止重复，每个 mask ，记录最大值和次大值即可
84.CF1063F String Journey
你倍增查询我也是服了，还从小到大，不应该是
2^{20}\rightarrow 2^{19}\rightarrow 2^{18} 吗你这是什么鬼??!!
int jump(int u,int len){
for(int j=0;j<=20;j++) if(t[f[u][j]].len>=len) u=f[u][j];
return u;
}都多少次了
for(int j=1;j<=20;j++) for(int i=1;i<=n;i++) f[i][j]=f[f[i][j-1]][j-1];
//错误代码
//你SAM上重建节点了还枚举到n????要到cnt为止吧
for(int j=1;j<=20;j++) for(int i=1;i<=cnt;i++) f[i][j]=f[f[i][j-1]][j-1];
//正确代码逻辑/三目运算符不要漏掉括号
bool check(){
return fi>=x-1;
}你这是要表(fi>=x)-1呢还是fi>=(x-1)呢
根据从左往右的顺序，表的是前面那个意，但是前面那么写没意义的啦，你一个check返回0/1，你这返回-1几个意思
代码别偷懒，好好写
return (fi>=(x-1));85.切割
点匹配区间，求最大匹配，用一个堆维护左端点不超过
a[i] 的右端点集合就行了，遇到一个a_i ，就拿出一个最小的右端点就行了当时一下糊涂了，思考下面三个代码为什么错误
sort(g+1,g+tot2+1,cmp);
for(int i=1;i<=tot1;i++) tag[a[i]]=1;
int i=1,j=0,pcnt=0,sum=0,tp=0;
for(i=1;i<=n;i++){
while(j+1<=tot2&&g[j+1].l<=i){
j++;p[g[j].r]++;if(g[j].r>=i) sum++;
}
if(tag[i]&&sum>0) pcnt++,sum--,tp++;
int t=min(p[i],tp);
p[i]-=t,tp-=t;
sum-=p[i];
}这个显然是错的，因为我们可能明明拿了区间
[l_1,r_1] 来匹配这个点，但是在之后扫的过程中又加进来一段区间[l_2,r_2],r_2<r_1 在我们这个代码中顶替了这段区间[l_1,r_1] 即我们的t ，减在p[r_2] 上了，这就错了
sort(g+1,g+tot2+1,cmp);
int i=1,j=1,pcnt=0;
for(i=1;i<=tot1;i++){
while(j<=tot2&&g[j].r<a[i]) ++j;
if(j<=tot2&&g[j].l<=a[i]) pcnt++,++j;
}这个反例太多了，就不举了，就是在满足区间
l 单调时，r 不一定单调
sort(g+1,g+tot2+1,cmp);
int i=1,j=0,pcnt=0;
for(i=1;i<=tot1;i++){
while(j+1<=tot2&&g[j+1].l<=a[i]){
j++;st.insert(g[j+1].r);//[1]
}
multiset<int >::iterator it=st.lower_bound(a[i]);
if(it!=st.end()){
st.erase(it);pcnt++;
}
}这份代码注意打
1 注释的地方，j++ 后了还要 j+1 吗？
86.[TJOI2018]游园会
int calc(int j,int t){
int mask;
for(int i=0;i<=k;i++) p[i]=0;
for(int i=1;i<=k;i++) p[i]=(j>>(i-1))&1;
for(int i=1;i<=k;i++) p[i]+=p[i-1];
for(int i=1;i<=k;i++){
p[i]=max(p[i],p[i-1]+(a[i]==t));//这个东西你都写的出来
}
for(int i=1;i<=k;i++) p[i]=max(p[i],p[i-1]);
mask=0;
for(int i=1;i<=k;i++) mask|=((p[i]-p[i-1])<<(i-1));
return mask;
}这是 dp套dp 的模板，然后里面套的是求 LCS 的 dp ，你难道没发现这份代码直接用
p[i-1] 加是第i 个字符是否匹配，并且它的i 是从1\rightarrow n 枚举过来的吗？注意，这样的话t 可能会匹配多个a_i !!!!应该倒着枚举
int calc(int j,int t){
int mask;
for(int i=0;i<=k;i++) p[i]=0;
for(int i=1;i<=k;i++) p[i]=(j>>(i-1))&1;
for(int i=1;i<=k;i++) p[i]+=p[i-1];
for(int i=k;i>=1;i--){
p[i]=max(p[i],p[i-1]+(a[i]==t));
}
for(int i=1;i<=k;i++) p[i]=max(p[i],p[i-1]);
mask=0;
for(int i=1;i<=k;i++) mask|=((p[i]-p[i-1])<<(i-1));
return mask;
}87.[POI2010]反对称
异或优先级很小，不加括号很容易与我们想表达的意思不同
比如，下面这份代码和再下面这份代码表达的意思是不一样的
while(s[i+len[i]]^s[i-len[i]]==1) ++len[i];
//上面这份表达的意思是(s[i+len[i]]^(s[i-len[i]==1))，与我们想要的结果截然不同while((s[i+len[i]]^s[i-len[i]])==1) ++len[i];88.「2017 山东一轮集训 Day4」基因
分块的时候，你块的个数设为
B 那么如果你希望空间尽量用满，请把单位块的长度设为n/B+2 以上，而不要n/B+1 ，因为你块的标号是从1 开始的，但是数组访问是从0 下标开始的！
89.[Ynoi2008] rdCcot
我们设md表示平衡树这个区间内最小的d值，那么注意平衡树pushup的时候，请先将md之类的初始化为这个点的d值。不然的话，它会保留之前的md值，干扰到取min的运算。
还有更新的时候一定要特判左右两边是否为空，这样不容易出错（给0赋极值的话在维护最小最大时比较麻烦）。
void pushup(int c){
t[c].sz=t[ls(c)].sz+t[rs(c)].sz+1;
t[c].md=t[c].dth;//值得注意的小细节
if(rs(c)) t[c].md=min(t[c].md,t[rs(c)].md);
if(ls(c)) t[c].md=min(t[c].md,t[ls(c)].md);return ;
}90.THUSC训练1集合
我写了个寂寞的平衡树，睁大你的眼睛，仔细看看你 merge 写的是什么东西，只有是随机数才能保证期望树高为
\log 。
int merge(int x,int y){
if(!x||!y) return x+y;
//if(t[x].val<t[y].val){pushdown(x);rs(x)=merge(rs(x),y);pushup(x);return x;}
if(t[x].rnd<t[y].rnd){pushdown(x);rs(x)=merge(rs(x),y);pushup(x);return x;}
pushdown(y);ls(y)=merge(x,ls(y));pushup(y);return y;
}看清楚，t[x].val 是权值，哪有按权值合并平衡树的啊，注意到我们树高期望
\log 是随机数保证的。错误2，线段树重载运算符的时候，是不保证结构体里的变量为
0 。这点大家都知道。但千万注意要把tag给清空，因为当我pushup的时候 t[c] 赋值为 t[ls(c)]+t[rs(c)] 时，由于重载后 tag 不为0 ，可能会导致多 pushdown 和覆盖。
91.省选训练34纵横中国
#define convex vector
convex f[N<<2][2][2];
void build(int c,int L,int R){
if(L==R){
f[c][0][0]={0};
f[c][1][1]={-inf,a[L]};
return ;
}
int mid=(L+R)>>1;build(ls(c),L,mid);build(rs(c),mid+1,R);
for(int l=0;l<2;l++){
convex f1=max(f[ls(c)][l][0],f[ls(c)][l][1]);
convex f2=max(f[ls(c)][l][0],Lshift(f[ls(c)][l][1]));
for(int r=0;r<2;r++){
f[c][l][r]=max(minkowski(f1,f[rs(c)][0][r]),minkowski(f2,f[rs(c)][1][r]));
}
}
return ;
}vector链表赋值的时候要开c++11，这个要注意，不然的话本地没问题，交上去就废了。注意NOIP是不开c++11的，所以vector链表赋值不要轻易使用，WC好像是可以用c++11的。如果不确定，可以在本题开个-std=c++98试试看会不会编译错误或者Warning。
可以尝试在用了c++11相关内容后，在题目最下方写上个"语言选c++11"的标签，防止真的出错。
ll dp[2],tmp[2];
void query(int c,int L,int R,int x,int y,ll k){
if(x<=L&&R<=y){
tmp[0]=dp[0],tmp[1]=dp[1];//sth wrong
//right answer:tmp[0]=-inf,tmp[1]=-inf;
for(int l=0;l<2;l++){
ll aa=max(dp[0],dp[1]);
ll bb=max(dp[0],dp[1]+k);
for(int r=0;r<2;r++){
if(E(f[c][l][r])) continue;
int lst=f[c][l][r].size()-1;
while(lst&&f[c][l][r][lst]-f[c][l][r][lst-1]<=k){f[c][l][r].pop_back();lst--;}
if(l==1){
tmp[r]=max(tmp[r],bb+f[c][l][r][lst]-lst*k);
}
tmp[r]=max(tmp[r],aa+f[c][l][r][lst]-lst*k);
}
}
dp[0]=tmp[0],dp[1]=tmp[1];
return ;
}
int mid=(L+R)>>1;
if(x<=mid) query(ls(c),L,mid,x,y,k);
if(y>mid) query(rs(c),mid+1,R,x,y,k);
return ;
}谁告诉你临时dp值存放处tmp直接赋dp[0],dp[1]的啊!
这样的话，会出现选择的是上个区间的右端点，当前区间右端点未被选择的情况，然后去与下一个区间左端点被选择的合并。这是导致我们出错的问题所在，我们的转移中出现了不合法的转移，即左右端点无法对接却按对接的方案去转移。以后dp的时候特别是滚动或者用临时变量存储的情况，千万小心初值的赋予!
92.THUSC训练4xor
无用操作太多，影响常数，影响均摊分析（你怎么这么点卡常能力都没有的啊!!!）
bool merge(int x,int y,int val){
int yx=x,yy=y;
x=find(x),y=find(y);
int tmp=xr[yx]^xr[yy];
if(x!=y){
if(mot){amonitor(x);amonitor(y);}
if(sz[x]>sz[y]) swap(x,y);
f[x]=y,sz[y]+=sz[x],xr[x]=tmp^val;
for(int i=0;i<=30;i++) ins(y,b[x][i]);
//应该写成下面这句话
for(int i=0;i<=30;i++) if(b[x][i]) ins(y,b[x][i]);
return 1;
}
return 0;
}你线性基插入次数是靠均摊分析来确定的，你这边把那些空的线性基也插入，平白多了许多常数啊，甚至复杂度都不正确。
还有注意线性基的小优化，就是你插满了就别再插入元素了!!!
int b[N][39];
void clr(int x){memset(b[x],0,sizeof(b[x]));cor[x]=30;return ;}
void ins(int c,int x){
if(!cor[c]) return ;
for(int i=30;i>=0;i--)
if((x>>i)&1){
if(!b[c][i]){b[c][i]=x,cor[c]--;return ;}
x^=b[c][i];
}
return ;
}还有注意并查集合并的时候对于
x,y 并不是都需要记录下他们原有的信息，因为我们复制个线性基是\log 的，所以要尽量减少复制的个数。
void odk(int x){
if(mot){
if(!flag[x]){
st[++top]=x,ok[top]=xr[x],OK[top]=f[x];
}
}
return ;
}
void amonitor(int x){
if(mot){
if(!flag[x]){
st[++top]=x,ok[top]=-1,flag[x]=1;
F[x]=f[x],SZ[x]=sz[x],XR[x]=xr[x];
for(int i=0;i<=30;i++) B[x][i]=b[x][i];Cor[x]=cor[x];
}
}
return ;
}
bool merge(int x,int y,int val){
int yx=x,yy=y;
x=find(x),y=find(y);
int tmp=oplus(yx)^oplus(yy);
if(x!=y){
if(sz[x]>sz[y]) swap(x,y);
if(mot){odk(x);amonitor(y);}
f[x]=y,sz[y]+=sz[x],xr[x]=tmp^val;
for(int i=0;i<=30;i++) if(b[x][i]) ins(y,b[x][i]);
return 1;
}
return 0;
}注意，并查集路径压缩会修改很多点的信息，会导致暴力撤销的时候常数巨大，所有题直接按秩合并就可以了，不会比路径压缩慢多少，反而在暴力撤销的时候快很多。
所以我们在选择按秩合并和路径压缩的时候注意是否需要回撤或者暴力撤销。通常这种时候光按秩合并是一个更好的选择。
93.[APIO2020]粉刷墙壁
前面起来ok[i]表示i这个点是否可以被转移，到后面反而没有去用？
//AC code
for(int i=m;i<n;i++){
if(ok[i]) dp[i]=t.sum(i-m)+1;
else dp[i]=t.tr[n+1];
t.add(i,dp[i]);
}还有注意这样转移的话，不合法的值会超过设的inf，所以判断无解的时候注意是>=inf
//AC code
if(!ok[m-1]) return -1;
t.n=n;t.begin();
dp[m-1]=1;t.add(m-1,1);
for(int i=m;i<n;i++){
if(ok[i]) dp[i]=t.sum(i-m)+1;
else dp[i]=t.tr[n+1];
t.add(i,dp[i]);
}
return (dp[n-1]>=t.tr[n+1])?(-1):dp[n-1];
94.CF1305G
注意光路径压缩的复杂度为
\log n ，不加启发式合并会被卡常。可以使用 cerr 代替 cout 输出非答案信息。会将信息输出到终端中，不影响评测。
95.CF1557A
本来结论对的,还自己瞎写什么乱七八糟的东西给罚时一发了。
ans=max(ans,aver(n-1,n)+aver(1,n-2));当n=2时，你这就直接输出两者的平均数了，而题目的要求是必须划分成两个子区间。虽然正数的时候是美什么问题的，但题目可以要求输入负数啊。
96.CF1557D
写了这么多年的线段树区间取 max，区间对 x 取 max ，还写挂！！
自己睁大眼睛看一看，下面两个有什么区别！
//version1
void upd(int c,pi x){if(t[c].mx<x){t[c].mx=x;t[c].tag=1;}return ;}
//你区间最大值比它大有什么用，要所有数都比它大才有不下传的资格，所有比它小的都要被更新。
//version2
void upd(int c,pi x){t[c].mx=max(t[c].mx,x),t[c].tag=max(t[c].tag,x);return ;}
下面那个是正确的。自己想想看，谁告诉你区间当前最大值比传进来的值大就可以不下传了啊？
很有可能是左半边有比它大的，右半边没有，还需要更新！并且你是区间对 x 取 max 。很有可能只有一个比 x 大的，那按照你这做法到了这个区间的点直接退出显然不对啊！tag 还是要打的，而且要一直打到孩子。除非你处理出来区间最小值比 x 大，才没有下传的意义。
积累到一种小 trick ，就是确定一个被限制的集合时可以逐位考虑。就是先考虑强制某个点必选，其它点随便可不可以最优/成立，跑一遍网络流/dp 之类的，然后枚举下一个。
另外一个小 trick 就是当我们要做加法时，发现利用的是一些依靠乘法的东西（如行列式，我要求完美匹配的权值和，而行列式相关的性质与乘积相关而不是加法），所以可以把这些数字给扔到指数上去，就变成乘法了。（加变乘）
2017 山东一轮集训 Day1 Sum
注意 NTT 跑一个长度为
m 的多项式乘法时，新的多项式长度会达到2m 次，如果你要继续调用这个多项式做多项式乘法时，记得手动把m+1 到2m 位清空。
AT1976
要清空两倍数组，只清空了一倍，这么低级的错误还在犯。
还有你这写的是什么鬼背包啊
f[n+1][0]=1;
for(int i=n;i>=1;i--)
for(int j=k-s[i].length();j>=0;j--)
if(f[i+1][j]) f[i][j+s[i].length()]=1,f[i][j]=1;原来就大于
k-s[i].length 的就不能更新了吗，你这明显每把j>s[i].length 更新到啊（对于那些不需要s[i].length 就可以达到的字符串拼接）。正确的代码应如下
f[n+1][0]=1;
for(int i=n;i>=1;i--)
for(int j=k;j>=0;j--){
if(f[i+1][j]){
f[i][j]=1;
if(j+s[i].length()<=k) f[i][j+s[i].length()]=1;
}
}AT2005
别把
n,m 变量名写反啊，注意下。
int find(ll x){
int l=1,r=m,ans=0;
//注意是 $m$ 而不是 $n$ ， $n$ 是初始的，不是后来的修改序列。
while(l<=r){
int mid=(l+r)>>1;
if(a[mid]<=x) l=mid+1,ans=mid;
else r=mid-1;
}
return ans;
}庆典
看到动态查询有向图（缩点后成 DAG 的题），一定要往树这个方面想啊，直接修改 DAG 然后维护怎么看都不科学啊，除非有更强的性质出现啊，看到这个性质若 x->z,y->z ，则x->y或y->x 一定要想到这个DAG拓扑后是棵树啊！
到了树上才是我们熟悉的可维护的东西啊。
for(int i=19;i>=0;i--) if(d[f[u][i]]!=d[f[v][i]]) u=f[u][i],v=f[v][i];
for(int i=1;i<=cnt;i++)
for(int j=1;j<20;j++) f[i][j]=f[f[i][j-1]][j-1];怀疑自己最近代码能力是不是为
0 啊,怎么倍增求 lca 都能写炸。以下为正确代码。
for(int i=19;i>=0;i--) if(f[u][i]!=f[v][i]) u=f[u][i],v=f[v][i];
//你要是正确代码的话，那 d[f[u][i]] 是一定等于 d[f[v][i]] 的啊。。。
for(int j=1;j<20;j++)
for(int i=1;i<=cnt;i++) f[i][j]=f[f[i][j-1]][j-1];
//还没填充进去就用这个值，是不是憨啊。
两个长度为
m 的多项式的卷积，在 NTT 过程中要维护2m 个点值，因为两个长度为m 的多项式乘积的结果为一个2m 次的多项式，需要2m 个点值才能还原其系数。至于只维护
m 个会出现什么情况，明确告诉你至少前\frac{m}{2} 个的系数都是错误的，你也不用考虑了，别犯这么没水平的错误就好了。明确长度
m 得两个多项式卷积，其长度要维护2m 位。
多少次了，多少次了，你 pushdown 标记不清空是干吗啊。标记永久化都不是你这么写的
pushdown标记清空，pushdown标记清空，pushdown标记清空
void pushdown(int c){
if(t[c].tag){
upd(ls(c));upd(rs(c));
t[c].tag=0;
}
if(t[c].tag2){
upd2(ls(c),t[c].tag2);
upd2(rs(c),t[c].tag2);
t[c].tag2=0;
}
}判断是否能够成一个多边形，只要看最大的那条边是否小于剩下的所有边的和。
不要再搞笑了，你写个构造函数 pp(int ii=0,int vv=0){id=ii,val=vv;} ，那你后面用的时候，肯定是 pp(i,v) 而不是 (i,v) 啊，这个错误很大，且难以看出来啊。
CF1582E
最大的 k 满足
\sum_{i=1}^{k}i\le n 的 k 是\sqrt{2n} 的，不要忘了2 。因为是(1+k)k/2\le n ，所以(1+k)k\le 2n ，所以是\sqrt{2n} 的，千万别落下2 ，不然错飞。
CF679D
哈哈，我居然用 db 是否有值来判断是否被加入集合过。
for(int k=1;k<=n;k++)
if(g[b][k]==1){
if(a[k]==0) v.push_back(k);
a[k]+=(db)1/(db)deg[b]/(db)n;
}
你会发现 1/400/400 和 0 进行比较会误判的。所以还是开个 int 表示是否遍历过就可以了。
CF627E
换根的时候没想到 dp 初值为
1 而非0 ，排序的时候应该是按 dp 值排序的，结果我按照编号大小排序。dp 初值赋完我又再特殊 case 上给它赋了个值，忘加
1 了。