坐标系上有n个目标，每个目标有一个价值，现在求一个边与坐标轴平行，边长为R的正方形，使在其内部（原题是不包括边界，然而实际上不是这样）的目标价值最大。
预处理一下以横纵坐标为节点的二维前缀和，然后枚举正方形右上角坐标即可。注意可以将坐标系向右上移动一个单位使前缀和不用考虑负数。反思：蒟蒻好弱啊，枚举时i和j的边界都应该是所以节点横坐标最大值与纵坐标最大值的最大值。蒟蒻一开始没注意到这一点，以为自己预处理写错。改来改去，WA来WA去。最后对着标程一点点改才发现问题。QAQ
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 5500
#define inc(i,j,k) for(int i=j;i<=k;i++)
using namespace std;
int sum[maxn][maxn],n,mxxy,r,mx;
int main(){
scanf("%d%d",&n,&r); mxxy=mx=0;
inc(i,1,n){
int x,y,z; scanf("%d%d%d",&x,&y,&z); x++; y++;
mxxy=max(mxxy,x); mxxy=max(mxxy,y); sum[x][y]+=z;
}
inc(i,1,mxxy)inc(j,1,mxxy)
sum[i][j]+=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
inc(i,r,mxxy)inc(j,r,mxxy)
mx=max(mx,sum[i][j]-sum[i][j-r]-sum[i-r][j]+sum[i-r][j-r]);
printf("%d",mx); return 0;
}N*M块地，如果两块地都没有障碍物，则互相可达。如果两块地互相可达（可经过其他地）则它们之间的距离为它们中心点的欧几里得距离，求如果能移走不大于T个障碍物，土地间的最大距离。N，M≤30
把经过一个障碍物视为边长度为1，求出每两个点之间要跨越的边长度，如果长度小于等于T，就将其欧几里得距离和答案比较。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cctype>
#define maxn 100
#define inc(i,j,k) for(int i=j;i<=k;i++)
using namespace std;
int map[maxn][maxn],n,m,k; double mx;
bool vis[maxn][maxn],inq[maxn][maxn]; int d[maxn][maxn];
struct qn{int x,y;}; queue <qn> q;
void spfa(int sx,int sy){
while(!q.empty())q.pop(); q.push((qn){sx,sy}); memset(d,-1,sizeof(d)); memset(inq,0,sizeof(inq));
memset(vis,0,sizeof(vis)); d[sx][sy]=map[sx][sy]; inq[sx][sy]=1;
while(!q.empty()){
qn x=q.front(); q.pop(); inq[x.x][x.y]=0;
if(x.x!=1&&(d[x.x-1][x.y]==-1||d[x.x-1][x.y]>d[x.x][x.y]+map[x.x-1][x.y])){
d[x.x-1][x.y]=d[x.x][x.y]+map[x.x-1][x.y];
if(!inq[x.x-1][x.y])inq[x.x-1][x.y]=1,q.push((qn){x.x-1,x.y});
}
if(x.y!=1&&(d[x.x][x.y-1]==-1||d[x.x][x.y-1]>d[x.x][x.y]+map[x.x][x.y-1])){
d[x.x][x.y-1]=d[x.x][x.y]+map[x.x][x.y-1];
if(!inq[x.x][x.y-1])inq[x.x][x.y-1]=1,q.push((qn){x.x,x.y-1});
}
if(x.x!=n&&(d[x.x+1][x.y]==-1||d[x.x+1][x.y]>d[x.x][x.y]+map[x.x+1][x.y])){
d[x.x+1][x.y]=d[x.x][x.y]+map[x.x+1][x.y];
if(!inq[x.x+1][x.y])inq[x.x+1][x.y]=1,q.push((qn){x.x+1,x.y});
}
if(x.y!=m&&(d[x.x][x.y+1]==-1||d[x.x][x.y+1]>d[x.x][x.y]+map[x.x][x.y+1])){
d[x.x][x.y+1]=d[x.x][x.y]+map[x.x][x.y+1];
if(!inq[x.x][x.y+1])inq[x.x][x.y+1]=1,q.push((qn){x.x,x.y+1});
}
}
inc(i,1,n)inc(j,1,m)if(d[i][j]<=k)vis[i][j]=1;
}
int main(){
scanf("%d%d%d",&n,&m,&k); char c;
inc(i,1,n)inc(j,1,m){
while(!isdigit(c=getchar())); map[i][j]=c-'0';
}
inc(i,1,n)inc(j,1,m){
spfa(i,j); inc(i0,1,n)inc(j0,1,m)if(vis[i0][j0])mx=max(mx,sqrt((i0-i)*(i0-i)+(j0-j)*(j0-j)));
}
printf("%.6lf",mx); return 0;
}n天，每天需要ai条消毒毛巾，这种消毒毛巾使用一天后必须再做消毒处理后才能使用。消毒方式有两种，A种方式的消毒需要a天时间，一条费用fA，B种方式的消毒需要b天，一条费用fB，买一块新毛巾的费用为f（新毛巾是已消毒的，当天可以使用），求最小费用。n≤1000
费用流。每天拆成x和y。s向所有x连边表示有的毛巾，所有y向t连边表示用的毛巾，流量为需要毛巾数费用0。xi向yi+a连边，表示a方式消毒，xi向yi+b连边，表示b方式消毒，s向所有y连边，表示买新的，xi向xi+1连边，表示前一天没用的拿到第二天用。反思：费用流关键是要抓住“流量优先”。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 3000
#define INF 0x3fffffff
using namespace std;
struct e{int f,t,c,w,n;}; e es[maxn*40]; int ess,g[maxn];
inline void pe(int f,int t,int c,int w){
es[++ess]=(e){f,t,c,w,g[f]}; g[f]=ess; es[++ess]=(e){t,f,0,-w,g[t]}; g[t]=ess;
}
void init(){ess=-1; memset(g,-1,sizeof(g));}
int d[maxn],fr[maxn]; bool inq[maxn]; queue <int> q;
bool spfa(int s,int t){
while(!q.empty())q.pop(); memset(inq,0,sizeof(inq)); memset(d,-1,sizeof(d));
inq[s]=1; d[s]=0; q.push(s); fr[s]=-1;
while(! q.empty()){
int x=q.front(); q.pop(); inq[x]=0;
for(int i=g[x];i!=-1;i=es[i].n)if(es[i].c&&(d[es[i].t]==-1||d[es[i].t]>d[x]+es[i].w)){
d[es[i].t]=d[x]+es[i].w; fr[es[i].t]=i; if(!inq[es[i].t])inq[es[i].t]=1,q.push(es[i].t);
}
}
return d[t]!=-1;
}
int advanced(int s,int t){
int a=INF,c=0;
for(int i=fr[t];i!=-1;i=fr[es[i].f])a=min(a,es[i].c);
for(int i=fr[t];i!=-1;i=fr[es[i].f])es[i].c-=a,es[i^1].c+=a,c+=(a*es[i].w);
return c;
}
int maxflowmincost(int s,int t){
int c=0; while(spfa(s,t))c+=advanced(s,t); return c;
}
int n,a,b,f,fa,fb,s,t,x;
int main(){
scanf("%d%d%d%d%d%d",&n,&a,&b,&f,&fa,&fb); s=0; t=2*n+1; init();
inc(i,1,n)scanf("%d",&x),pe(s,i,x,0),pe(n+i,t,x,0);
inc(i,1,n){
if(i+a<n)pe(i,n+i+a+1,INF,fa); if(i+b<n)pe(i,n+i+b+1,INF,fb);
if(i<n)pe(i,i+1,INF,0); pe(s,i+n,INF,f);
}
printf("%d",maxflowmincost(s,t)); return 0;
}数轴上N个点，分为K种。可以有多个点出现在同一个位置上。需要一个最短区间使里面有K种点，求这个区间长度。N≤1000000
先排序，然后用两个指针分别指向区间两个端点，每次l指针往左移并更新答案直到区间里没有K种点，再把r指针向右移直到区间里有K种点，更新一下答案。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define INF 0x3fffffff
using namespace std;
struct ball{int a,b;}; ball balls[1000500];
bool cmp(ball a,ball b){return a.a<b.a;}
int n,k,l,r,bs,kn[70],ks,mn;
int main(){
scanf("%d%d",&n,&k);
inc(i,1,k){
int x,y; scanf("%d",&x); inc(j,1,x)scanf("%d",&y),balls[++bs]=(ball){y,i};
}
sort(balls+1,balls+1+bs,cmp); l=1; r=0;
memset(kn,0,sizeof(kn)); ks=0; mn=INF;
while(ks<k){
if(r<n){r++; kn[balls[r].b]++; if(kn[balls[r].b]==1)ks++;}
while(r<n&&balls[r].a==balls[r+1].a){r++; kn[balls[r].b]++; if(kn[balls[r].b]==1)ks++;}
if(r==n)break;
}
if(ks==k)mn=min(mn,balls[r].a-balls[l].a);
while(1){
while(l<r&&balls[l].a==balls[l+1].a){kn[balls[l].b]--; if(kn[balls[l].b]==0)ks--; l++;}
if(l<r){kn[balls[l].b]--; if(kn[balls[l].b]==0)ks--; l++;}
if(ks==k)mn=min(mn,balls[r].a-balls[l].a);else{
while(ks<k){
if(r<n){r++; kn[balls[r].b]++; if(kn[balls[r].b]==1)ks++;}
while(r<n&&balls[r].a==balls[r+1].a){r++; kn[balls[r].b]++; if(kn[balls[r].b]==1)ks++;}
if(r==n)break;
}
if(ks==k)mn=min(mn,balls[r].a-balls[l].a);
}
if(l==r)break;
}
printf("%d",mn); return 0;
}给个树，每次给三个点，求与这三个点距离最小的点。
倍增求出两两之间的LCA后，比较容易理解的做法是挑出两个LCA再做一次LCA，比较所有挑法。但画kan出ti图jie可知其中有两个LCA是相等的，而所求就是那个与它们不等的LCA（我也不知为什么）。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 500500
#define inc(i,j,k) for(int i=j;i<=k;i++)
using namespace std;
inline int read(){
char ch=getchar(); int f=1,x=0;
while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*f;
}
int fa[maxn][20],dep[maxn];
struct e{int t,n;}; e es[maxn*2]; int g[maxn],ess;
void pe(int f,int t){
es[++ess]=(e){t,g[f]}; g[f]=ess; es[++ess]=(e){f,g[t]}; g[t]=ess;
}
void init(){ess=0; memset(g,0,sizeof(g));}
void dfs(int x,int f){
for(int i=g[x];i;i=es[i].n)if(es[i].t!=f){
dep[es[i].t]=dep[x]+1; fa[es[i].t][0]=x; dfs(es[i].t,x);
}
}
int n,m;
void build(){
for(int j=1;(1<<j)<=n;j++)inc(i,1,n)fa[i][j]=fa[fa[i][j-1]][j-1];
}
int lca(int x,int y){
if(dep[x]<dep[y])swap(x,y); int t=dep[x]-dep[y];
for(int i=0;(1<<i)<=n;i++)if(t&(1<<i))x=fa[x][i];
for(int i=18;i>=0;i--)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
if(x==y)return x;else return fa[x][0];
}
int dis(int x,int y){
int z=lca(x,y); return dep[x]-dep[z]+dep[y]-dep[z];
}
int main(){
n=read(); m=read(); init(); inc(i,1,n-1){int a=read(),b=read(); pe(a,b);}
dep[1]=0; fa[1][0]=0; dfs(1,0); build();
inc(i,1,m){
int a=read(),b=read(),c=read(); int x=lca(a,b),y=lca(a,c),z=lca(b,c);
if(x==y)printf("%d %d\n",z,dis(a,z)+dis(b,z)+dis(c,z));
else if(x==z)printf("%d %d\n",y,dis(a,y)+dis(b,y)+dis(c,y));
else if(y==z)printf("%d %d\n",x,dis(a,x)+dis(b,x)+dis(c,x));
}
return 0;
}n个小朋友通过投票来决定睡不睡午觉。每个人都有自己的主见，但也可以投和自己本来意愿相反的票。冲突总数为好朋友之间发生冲突的总数加上和自己本来意愿发生冲突的人数。求最小冲突数。
最小割，s向每个选1的人连边流量为1，每个选0的人连边流量为1。好朋友之间连流量为1的双向边。反思：理解错题意……以为冲突总数是每个人投票的冲突数之和，每个人投票冲突数是与朋友之间发生冲突的总数加上和这个人本来意愿发生冲突的人数。脑洞好大QAQ
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define maxn 500
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define INF 0x3fffffff
using namespace std;
struct e{int t,c,n;}; e es[maxn*2000]; int g[maxn],ess;
inline void pe(int f,int t,int c){
es[++ess]=(e){t,c,g[f]}; g[f]=ess; es[++ess]=(e){f,0,g[t]}; g[t]=ess;
}
inline void pe2(int f,int t,int c){
es[++ess]=(e){t,c,g[f]}; g[f]=ess; es[++ess]=(e){f,c,g[t]}; g[t]=ess;
}
inline void init(){
ess=-1; memset(g,-1,sizeof(g));
}
queue <int> q; int h[maxn];
bool bfs(int s,int t){
memset(h,-1,sizeof(h)); while(!q.empty())q.pop(); h[s]=0; q.push(s);
while(! q.empty()){
int x=q.front(); q.pop();
for(int i=g[x];i!=-1;i=es[i].n)if(es[i].c&&h[es[i].t]==-1)h[es[i].t]=h[x]+1,q.push(es[i].t);
}
return h[t]!=-1;
}
int dfs(int x,int t,int f){
if(x==t)return f; int u=0;
for(int i=g[x];i!=-1;i=es[i].n)if(es[i].c&&h[es[i].t]==h[x]+1){
int w=dfs(es[i].t,t,min(f,es[i].c)); f-=w; u+=w; es[i].c-=w; es[i^1].c+=w; if(f==0)return u;
}
if(u==0)h[x]=-1; return u;
}
int dinic(int s,int t){
int f=0; while(bfs(s,t))f+=dfs(s,t,INF); return f;
}
inline int read(){
char ch=getchar(); int f=1,x=0;
while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*f;
}
int n,m,s,t;
int main(){
n=read(); m=read(); s=0; t=n+1; init(); inc(i,1,n){int x=read(); if(x)pe(s,i,1);else pe(i,t,1);}
inc(i,1,m){int x=read(),y=read(); pe2(x,y,1);} printf("%d",dinic(s,t)); return 0;
}n*m矩阵，支持两个操作，修改某个格子权值和查询某个子矩阵特定权值出现次数。n，m≤300，权值为1到100的整数。
原来二维前缀和也可以用树状数组维护，只要那个不断增加/减少lowbit的循环再嵌套一层就行了。同时因为权值是1到100的整数，所以二维前缀和多一维维护特定权值个数就行了。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 301
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define lb(x) x&-x
using namespace std;
int sm[maxn][maxn][maxn/3+1],col[maxn][maxn],n,m;
void update(int x,int y,int z,int v){
for(int i=x;i<=n;i+=lb(i))for(int j=y;j<=m;j+=lb(j))sm[i][j][z]+=v;
}
int query(int x,int y,int z){
int q=0; for(int i=x;i>=1;i-=lb(i))for(int j=y;j>=1;j-=lb(j))q+=sm[i][j][z]; return q;
}
inline int read(){
char ch=getchar(); int f=1,x=0;
while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return f*x;
}
int main(){
n=read(); m=read(); inc(i,1,n)inc(j,1,m){col[i][j]=read(); update(i,j,col[i][j],1);} int q=read();
inc(i,1,q){
int x=read();
if(x==1){
int x0=read(),x1=read(),x2=read();
update(x0,x1,col[x0][x1],-1); update(x0,x1,x2,1); col[x0][x1]=x2;
}
if(x==2){
int x1=read(),x2=read(),y1=read(),y2=read(),c=read();
printf("%d\n",query(x2,y2,c)-query(x1-1,y2,c)-query(x2,y1-1,c)+query(x1-1,y1-1,c));
}
}
return 0;
}输出1到n-1中平方后模n等于1的整数
设所求数x，化简得(x+1)(x-1)=n*k，设n1*n2等于k,(x+1)%n1==0，(x-1)%n2==0，因此n1、n2都为n的因数，且一个≤sqrt(n)，一个≥(sqrt(n))。据说int以内的数的因数都不超过30个，所以可以先求出所有≥sqrt(n)的因数，然后对于每个因数，求出所有＜n的这个因数的倍数，用它尝试被x+1模。因为这些因数都≥sqrt(n)，所以这个枚举的过程不会超时。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 100
using namespace std;
int yss,ys[maxn],st[maxn*5000],sts;
int main(){
int n; scanf("%d",&n); inc(i,1,(int)sqrt(n))if(n%i==0)ys[++yss]=n/i; st[sts=1]=1;
inc(i,1,yss){
for(int j=ys[i];j<=n;j+=ys[i]){
if((j-2)%(n/ys[i])==0)st[++sts]=j-1;
if(j<n&&(j+2)%(n/ys[i])==0)st[++sts]=j+1;
}
}
if(sts==0||n==1)printf("None");else{
sort(st+1,st+1+sts); int m=unique(st+1,st+1+sts)-st-1; inc(i,1,m)printf("%d\n",st[i]);
}
return 0;
}r行c列网格图上有一些高低不平的柱子，一些柱子上有蜥蜴，一只蜥蜴一次能跳距离为d，每次蜥蜴跳跃时出发柱子高度减一，当柱子高度为0时消失，问最少多少蜥蜴不能跳出网格图。r，c≤20，d≤4
裸最大流，每个柱子拆成X，Y两点，两点之间连柱子的高度，所有Yi向可达柱子的Xi连边，s向所有蜥蜴初始位置连边，所有可以跳出图的柱子向t连边。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define maxn 1000
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define INF 0x3fffffff
using namespace std;
struct e{int t,c,n;}; e es[maxn*40]; int g[maxn],ess;
inline void pe(int f,int t,int c){
es[++ess]=(e){t,c,g[f]}; g[f]=ess; es[++ess]=(e){f,0,g[t]}; g[t]=ess;
}
inline void init(){
ess=-1; memset(g,-1,sizeof(g));
}
queue <int> q; int h[maxn];
bool bfs(int s,int t){
memset(h,-1,sizeof(h)); while(!q.empty())q.pop(); h[s]=0; q.push(s);
while(! q.empty()){
int x=q.front(); q.pop();
for(int i=g[x];i!=-1;i=es[i].n)if(es[i].c&&h[es[i].t]==-1)h[es[i].t]=h[x]+1,q.push(es[i].t);
}
return h[t]!=-1;
}
int dfs(int x,int t,int f){
if(x==t)return f; int u=0;
for(int i=g[x];i!=-1;i=es[i].n)if(es[i].c&&h[es[i].t]==h[x]+1){
int w=dfs(es[i].t,t,min(f,es[i].c)); f-=w; u+=w; es[i].c-=w; es[i^1].c+=w; if(f==0)return u;
}
if(u==0)h[x]=-1; return u;
}
int dinic(int s,int t){
int f=0; while(bfs(s,t))f+=dfs(s,t,INF); return f;
}
inline int dis(int x1,int y1,int x2,int y2){
return (x2-x1)*(x2-x1)+(y2-y1)*(y2-y1);
}
int r,c,d,s,t,pos[30][30],x[500],y[500],he[500],n,tot; char str[30];
int main(){
scanf("%d%d%d",&r,&c,&d); n=tot=0;
inc(i,1,r){
scanf("%s",str);
inc(j,0,c-1)if(str[j]!='0')
n++,x[n]=i,y[n]=j+1,he[n]=str[j]-'0',pos[i][j+1]=n;
}
init(); s=0; t=2*n+1;
inc(i,1,r){
scanf("%s",str);
inc(j,0,c-1)if(str[j]=='L')pe(s,pos[i][j+1],1),tot++;
}
inc(i,1,n){
pe(i,n+i,he[i]);
inc(j,1,n)if(i!=j&&dis(x[i],y[i],x[j],y[j])<=d*d)pe(n+i,j,INF);
if(x[i]<=d||r+1-x[i]<=d||y[i]<=d||c+1-y[i]<=d)pe(n+i,t,INF);
}
printf("%d",tot-dinic(s,t)); return 0;
}一个n点树，根节点为1，初始时全部边为土路，共n-m+1次操作，每次可将一条边改为公路或求根节点到某个节点要几个多少土路。n，m≤250000
先求出DFS序，进入节点在时间点的权值为1，离开节点在时间点的权值为-1，如果把公路转成土路就将这条边的左端点的进入时间权值和离开时间权值都置为0，如果询问则输出节点进入时间前缀和。求前缀和及修改的操作可以用树状数组维护。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 250500
#define lb(x) x&-x
using namespace std;
struct e{int t,n;}; e es[maxn]; int g[maxn],ess;
void pe(int f,int t){
es[++ess]=(e){t,g[f]}; g[f]=ess;
}
int st[maxn*2],l[maxn],r[maxn],tim;
void dfs(int x){
st[++tim]=x; l[x]=tim;
for(int i=g[x];i;i=es[i].n)dfs(es[i].t);
st[++tim]=x; r[x]=tim;
}
inline int read(){
char ch=getchar(); int f=1,x=0;
while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return f*x;
}
int c[maxn*2],n;
void update(int x,int v){while(x<=n*2)c[x]+=v,x+=lb(x);}
int query(int x){int q=0; while(x)q+=c[x],x-=lb(x); return q;}
int main(){
n=read(); inc(i,1,n-1){int a=read(),b=read(); pe(a,b);}
dfs(1); inc(i,1,n)update(l[i],1),update(r[i],-1);
int m=read(); char opt[3];
inc(i,1,n+m-1){
scanf("%s",opt);
if(opt[0]=='W'){int a=read(); printf("%d\n",query(l[a])-1);}
if(opt[0]=='A'){int a=read(),b=read(); update(l[b],-1); update(r[b],1);}
}
return 0;
}n个节点，每个节点有个权值，初始时有m次连通两点的操作，接下来有q次操作，每次可以连通两个点或求某个点所在连通块权值第k小的节点编号。n，m≤100000，q≤300000
treap启发式合并，就是暴力将小的树拆了插到大的树里，均摊复杂度O(log^2n)。由于本弱用的是treap，不能维护fa数组，所以要并查集维护根节点。如果是splay就不用。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <queue>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 100500
using namespace std;
int fa[maxn],rt[maxn],ch[maxn][2],v[maxn],sz[maxn],rnd[maxn];
void update(int x){
sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+1;
}
void rot(int &x,bool lr){
if(!x)return; int a=ch[x][lr]; ch[x][lr]=ch[a][!lr]; ch[a][!lr]=x;
update(x); update(a); x=a;
}
void insert(int &x,int y){
if(!x){x=y; return;}
if(v[y]<v[x])insert(ch[x][0],y);else insert(ch[x][1],y); update(x);
if(ch[x][0]&&rnd[ch[x][0]]<rnd[x])rot(x,0);
if(ch[x][1]&&rnd[ch[x][1]]<rnd[x])rot(x,1);
}
int find(int x,int k){
if(sz[x]<k)return -1;
if(sz[ch[x][0]]==k-1)return x;
if(sz[ch[x][0]]<k-1)return find(ch[x][1],k-sz[ch[x][0]]-1);
if(sz[ch[x][0]]>k-1)return find(ch[x][0],k);
}
queue <int> q;
int fd(int x){return x==fa[x]?x:fa[x]=fd(fa[x]);}
void merge(int xx,int yy){
int x=fd(xx),y=fd(yy); if(x==y)return; if(sz[rt[x]]>sz[rt[y]])swap(x,y);
fa[x]=y; while(! q.empty())q.pop(); q.push(rt[x]); y=rt[y];
while(! q.empty()){
int z=q.front(); q.pop(); sz[z]=1;
if(ch[z][0])q.push(ch[z][0]); if(ch[z][1])q.push(ch[z][1]);
ch[z][0]=ch[z][1]=0; insert(y,z);
}
rt[fa[x]]=y;
}
inline int read(){
char ch=getchar(); int f=1,x=0;
while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return f*x;
}
int n,m;
int main(){
n=read(); m=read();
inc(i,1,n)
v[i]=read(),ch[i][0]=ch[i][1]=0,rnd[i]=rand(),fa[i]=rt[i]=i,sz[i]=1;
inc(i,1,m){int a=read(),b=read(); merge(a,b);}
m=read(); char opt[3];
inc(i,1,m){
scanf("%s",opt);
if(opt[0]=='Q'){
int a=read(),b=read(); printf("%d\n",find(rt[fd(a)],b));
}
if(opt[0]=='B'){
int a=read(),b=read(); merge(a,b);
}
}
return 0;
}t组数据，每组n个给出两个变量是相等还是不等的约束条件，要求判断是否能满足。n≤1000000，变量数量≤10^9
先离散化，然后只处理相等条件用并查集维护“相等集合”，接着对每个不相等条件判断是否在一个集合，是的话则说明不满足。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define maxn 1000100
#define inc(i,j,k) for(int i=j;i<=k;i++)
using namespace std;
inline int read(){
char ch=getchar(); int f=1,x=0;
while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return f*x;
}
int t,n;
struct opt{int a,b; bool c;}; opt opts[maxn];
struct ls{int a,c; bool b;}; ls lss[maxn*2]; int lsss,tot,fa[maxn*2];
bool cmp(ls a,ls b){return a.a<b.a;}
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
int main(){
t=read(); while(t--){
n=read(); lsss=0;
inc(i,1,n){
int a=read(),b=read(); opts[i].c=read();
lss[++lsss]=(ls){a,i,0}; lss[++lsss]=(ls){b,i,1};
}
sort(lss+1,lss+lsss+1,cmp); tot=0;
inc(i,1,lsss){
if(i==1||lss[i].a!=lss[i-1].a)tot++;
if(!lss[i].b)opts[lss[i].c].a=tot;else opts[lss[i].c].b=tot;
}
inc(i,1,tot)fa[i]=i;
inc(i,1,n)if(opts[i].c){
int x=find(opts[i].a),y=find(opts[i].b); if(x!=y)fa[x]=y;
}
bool f=0;
inc(i,1,n)if(!opts[i].c){
int x=find(opts[i].a),y=find(opts[i].b); if(x==y){f=1; break;}
}
if(f)puts("NO");else puts("YES");
}
return 0;
}给出一个字符串，要求求出形如A+B+A的子串数量，且lenA≥k，lenB≥1。字符串长度≤15000，k≤100，所以字符长度为小写字母。
第一次写kmp的题QAQ~这题利用的是fail函数的性质：若字符串s在位置x的fail函数f[x]不为0，则prefix(s+1,s+x)的长度为f[x]的前缀和长度为f[x]的后缀相同。因此枚举每个后缀为为j，对这个后缀做kmp，再递推一个令f[i]-j+1≥k且最小的f[i]为last[x]（f[i]表示i=x; while(i>=后缀位)i=f[i]得到的所有f[i]），若last[x]-j小于等于(x-j)/2则子串(j,x)合法。讲的很乱，具体看代码。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define INF 0x3fffffff
using namespace std;
char s[15100]; int l,k,next[15100],last[15100],ans;
int main(){
//freopen("in.txt","r",stdin);
scanf("%s",s+1); l=strlen(s+1); scanf("%d",&k); ans=0;
inc(i,1,l){
next[i]=i-1; last[i]=INF;
inc(ii,i+1,l){
int j=next[ii-1]; while(j>=i&&s[ii]!=s[j+1])j=next[j];
if(s[ii]==s[j+1])next[ii]=j+1;else next[ii]=j;
if(next[ii]-i+1<k)last[ii]=INF;else{
last[ii]=min(last[next[ii]],next[ii]);
if(last[ii]-i+1<=(ii-i)>>1)ans++;//,printf("%d %d\n",i,ii);
}
}
}
printf("%d",ans); return 0;
}T组数据，每组给出两个三角形各点坐标，要求求出一个点使第一个三角形可以绕这个点放缩和旋转得到另一个三角形。T≤10，坐标为≤10000的实数，数据保证三角形不用平移，答案保留三位小数。
复数既是一种数，又可以当做一种独特的二维向量，因为其数的特点可以用来解方程，又因为其向量的特点可以表示二维的点和变换。两个复数的积在几何上定义为把它转化为向量后极角相加，长度相乘，正可以用来表示放缩和旋转变换。因此设A，B，C为变换前三角形三个顶点（用复数表示），T为变换复数，P为绕的那个点，A’，B’，C’表示变换后的点。于是可以列方程(A-P)*T=(A’-P) (B-P)*T=(B’-P) (C-P)*T=(C’-P)，我们可以枚举A，B，C分别是第一个三角形的哪个顶点，然后联立前两道解出T代入第三道验证。然而本傻逼忘记枚举了导致WA了好几发，顺便安利STL的complex类，已经包装好了复数的常用运算。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <complex>
#define inc(i,j,k) for(int i=j;i<=k;i++)
using namespace std;
complex <double> a,b,c,d,e,f,t,p,g;
int T;
int main(){
scanf("%d",&T); while(T--){
double x,y;
scanf("%lf%lf",&x,&y); a.real(x); a.imag(y);
scanf("%lf%lf",&x,&y); b.real(x); b.imag(y);
scanf("%lf%lf",&x,&y); c.real(x); c.imag(y);
scanf("%lf%lf",&x,&y); d.real(x); d.imag(y);
scanf("%lf%lf",&x,&y); e.real(x); e.imag(y);
scanf("%lf%lf",&x,&y); f.real(x); f.imag(y);
g.real(1.000000),g.imag(0.000000); t=(e-d)/(b-a); p=(a*t-d)/(t-g);
if(abs(((c-p)*t-(f-p)).real())<1e-4&&abs(((c-p)*t-(f-p)).imag())<1e-4){
printf("%.6lf %.6lf\n",p.real(),p.imag()); continue;
}
swap(b,c); t=(e-d)/(b-a); p=(a*t-d)/(t-g);
if(abs(((c-p)*t-(f-p)).real())<1e-4&&abs(((c-p)*t-(f-p)).imag())<1e-4){
printf("%.6lf %.6lf\n",p.real(),p.imag()); continue;
}
swap(a,b); t=(e-d)/(b-a); p=(a*t-d)/(t-g);
if(abs(((c-p)*t-(f-p)).real())<1e-4&&abs(((c-p)*t-(f-p)).imag())<1e-4){
printf("%.6lf %.6lf\n",p.real(),p.imag()); continue;
}
swap(b,c); t=(e-d)/(b-a); p=(a*t-d)/(t-g);
if(abs(((c-p)*t-(f-p)).real())<1e-4&&abs(((c-p)*t-(f-p)).imag())<1e-4){
printf("%.6lf %.6lf\n",p.real(),p.imag()); continue;
}
swap(a,b); t=(e-d)/(b-a); p=(a*t-d)/(t-g);
if(abs(((c-p)*t-(f-p)).real())<1e-4&&abs(((c-p)*t-(f-p)).imag())<1e-4){
printf("%.6lf %.6lf\n",p.real(),p.imag()); continue;
}
swap(b,c); t=(e-d)/(b-a); p=(a*t-d)/(t-g);
if(abs(((c-p)*t-(f-p)).real())<1e-4&&abs(((c-p)*t-(f-p)).imag())<1e-4){
printf("%.6lf %.6lf\n",p.real(),p.imag()); continue;
}
}
return 0;
}给个n点树，再给个节点的游览顺序，每经过一个节点（包括上一个游览的点到下一个游览的点路径上的点）就可以从这个节点拿走一个糖，问所有节点一开始要放几个糖。最后到达的节点不用糖。n≤300000
链剖将树链排成一列，然后用数组区间加的方式（即在数组区间左端点位置增加值，数组区间右端点+1位置增加这个值的相反数，最后扫一遍a[i]+=a[i-1]）累计糖果数。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 300100
#define inc(i,j,k) for(int i=j;i<=k;i++)
using namespace std;
inline int read(){
char ch=getchar(); int f=1,x=0;
while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*f;
}
struct e{int t,n;}; e es[maxn*2]; int g[maxn],ess;
void pe(int f,int t){
es[++ess]=(e){t,g[f]}; g[f]=ess; es[++ess]=(e){f,g[t]}; g[t]=ess;
}
void init(){ess=0; memset(g,0,sizeof(g));}
int n,fa[maxn],dep[maxn],go[maxn],pos[maxn],top[maxn],sz[maxn],sm[maxn],tot;
void dfs1(int x,int f){
sz[x]=1;
for(int i=g[x];i;i=es[i].n)if(es[i].t!=f){
dep[es[i].t]=dep[x]+1; fa[es[i].t]=x;
dfs1(es[i].t,x); sz[x]+=sz[es[i].t];
}
}
void dfs2(int x,int f,int tp){
pos[x]=++tot; top[x]=tp; int mx=0;
for(int i=g[x];i;i=es[i].n)if(es[i].t!=f){
if(!mx||sz[mx]<sz[es[i].t])mx=es[i].t;
}
if(!mx)return; dfs2(mx,x,tp);
for(int i=g[x];i;i=es[i].n)if(es[i].t!=f&&es[i].t!=mx){
dfs2(es[i].t,x,es[i].t);
}
}
void lca(int x,int y){
for(;top[x]!=top[y];sm[pos[top[x]]]++,sm[pos[x]+1]--,x=fa[top[x]])
if(dep[top[x]]<dep[top[y]])swap(x,y);
if(dep[x]>dep[y])swap(x,y); sm[pos[x]]++,sm[pos[y]+1]--;
}
int main(){
n=read(); inc(i,1,n)go[i]=read(); init();
inc(i,1,n-1){int a=read(),b=read(); pe(a,b);}
dep[1]=0; fa[1]=0; tot=0; dfs1(1,0); dfs2(1,0,1);
inc(i,1,n){
if(i==1){sm[pos[go[i]]]++; sm[pos[go[i]]+1]--; continue;}
sm[pos[go[i-1]]]--; sm[pos[go[i-1]]+1]++; lca(go[i-1],go[i]);
if(i==n){sm[pos[go[i]]]--; sm[pos[go[i]]+1]++;}
}
inc(i,1,tot)sm[i]+=sm[i-1]; inc(i,1,n)printf("%d\n",sm[pos[i]]);
return 0;
}给n个数Ai，n个数Bi，将Ai中的数与Bi中的数配对，求配对Ai比Bi大的比Bi比Ai大的恰好有k组的方案数。n，k≤2000
蒟蒻太弱了只能引用神犇题解
我们将两个读入的数组排序,令 next[i] 表示最大的 j 满足 A[i]>B[j],令f[i][j]表示枚举到第i个A时，有j组A>B，但剩下的情况是不考虑的，则f[i][j]=f[i-1][j]+f[i-1][j-1]*(next[i]-j+1)。但若把 f[n][s] 直接输出会WA因为会有这种情况出现: a1，a2，a3 b1，b2，b3 a1>b1 a2>b2 a3>b3 那么((a1，b1)，(a2，b2)，a3不明)和((a1，b1)，(a3，b3)，a2不明)就会被视为两种答案，可见我们要求出的是 f’[n][s] 表示n个A，有s组A>B，剩下的都是B>A 这里就要用容斥了
\[ f'[n][i]=f[n][i]\times(n-i)!-\sum_{j=i+1}^n{f'[n][j]*C[j][i]} \]
(n-i)!是枚举后面 n-i 可能的方案，f‘[n][j]*C(j, i) 表示 f[n][i] 中实际有 j 组B>A却被计入f[n][i]的数量 f’[n][s]就是答案了，总时间复杂度为 O(n^2)
C(j,i)要递推，不然要溢出。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define dec(i,j,k) for(int i=j;i>=k;i--)
#define maxn 2100
#define mod 1000000009
#define ll long long
using namespace std;
int s[maxn],p[maxn],next[maxn],n,k; ll f1[maxn][maxn],f2[maxn],C[maxn][maxn],P[maxn];
inline int read(){
char ch=getchar(); int f=1,x=0;
while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return f*x;
}
int main(){
n=read(); k=read(); if((n-k)&1){printf("0"); return 0;} k=((n-k)>>1)+k;
inc(i,1,n)s[i]=read(); inc(i,1,n)p[i]=read(); sort(s+1,s+n+1); sort(p+1,p+n+1);
int l=1; inc(i,1,n){while(p[l]<s[i]&&l<=n)l++; next[i]=l-1;}
f1[0][0]=1; inc(i,1,n){f1[i][0]=1; inc(j,1,n)f1[i][j]=(f1[i-1][j]+f1[i-1][j-1]*(ll)max(next[i]-j+1,0)%mod)%mod;}
P[0]=1; inc(i,1,n)P[i]=P[i-1]*(ll)i%mod;
inc(i,0,n){C[i][0]=1; inc(j,1,i)C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;}
dec(i,n,k){
f2[i]=0; inc(j,i+1,n)f2[i]=(f2[i]+f2[j]*C[j][i]%mod)%mod;
f2[i]=f1[n][i]*P[n-i]%mod-f2[i]; if(f2[i]<0)f2[i]+=mod;
}
printf("%lld",f2[k]); return 0;
}给出N个数，要求把其中重复的去掉，只保留第一次出现的数。n≤50000
一道令管理员都后悔加入的水题，按大小排序后unique，再按读入顺序排序即可。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define inc(i,j,k) for(int i=j;i<=k;i++)
using namespace std;
inline int read(){
char ch=getchar(); int f=1,x=0;
while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return f*x;
}
int t,n,tot;
struct nd{int v,id;};
bool cmp1(nd a,nd b){if(a.v!=b.v)return a.v<b.v;else return a.id<b.id;}
bool cmp2(nd a,nd b){return a.id<b.id;};
nd a[50010],b[50010];
int main(){
t=read(); while(t--){
n=read(); inc(i,1,n)a[i].v=read(),a[i].id=i; sort(a+1,a+n+1,cmp1); tot=0;
inc(i,1,n)if(i==1||a[i].v!=a[i-1].v)b[++tot]=a[i]; sort(b+1,b+tot+1,cmp2);
inc(i,1,tot-1)printf("%d ",b[i].v); printf("%d\n",b[tot].v);
}
return 0;
}n个野人，分为k个部落，两个部落之间距离定义为两个部落最近两个野人的距离，要求划分时最近的部落最远。求这种划分下部落间最近距离。n，k≤1000，野人坐标≤10000是整数。
每次将两个部落连接，则这两个部落之间的距离则消失，因此我们应尽力让那些比较短的边消失，所以先O(n2)弄出野人间两两的边，将它们按距离从小到大排序，然后用类似Kruscal的方法（其实就是Kruscal）连边，最后连的边的下一条可连的边的长度就是所求。注意最后的退出条件是cnt==n-k+1。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 1010
using namespace std;
struct e{int f,t,dis;}; e es[maxn*maxn/2]; int ess;
bool cmp(e a,e b){return a.dis<b.dis;}
int x[maxn],y[maxn],fa[maxn],n,k;
inline int read(){
char ch=getchar(); int f=1,x=0;
while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return f*x;
}
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
int main(){
n=read(); k=read(); inc(i,1,n)x[i]=read(),y[i]=read(); ess=0;
inc(i,1,n)inc(j,i+1,n)es[++ess]=(e){i,j,(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])};
sort(es+1,es+ess+1,cmp); int cnt=0; inc(i,1,n)fa[i]=i;
inc(i,1,ess){
int x=find(es[i].f),y=find(es[i].t); if(x==y)continue; fa[x]=y; cnt++;
if(cnt==n-k+1){printf("%.2lf",sqrt(es[i].dis)); break;}
}
return 0;
}给个根节点为1的n点树，初始时节点1标记，Q个操作，每次可以标记一个点或求一个点最近一个标记了的祖先。
链剖可以写，当正解应该是并查集。离线读入所有操作，累加每个节点的标记次数，之后所有未被标记的节点向其父亲节点连边，然后倒着来，如果操作是询问则输出这个节点在并查集中的根节点，如果是标记则将该节点的标记数减1，一旦这个节点的标记数减到了0，就让它向父亲节点连边。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define dec(i,j,k) for(int i=j;i>=k;i--)
#define maxn 100100
using namespace std;
inline int read(){
char ch=getchar(); int f=1,x=0;
while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return f*x;
}
struct e{int t,n;}; e es[maxn*2]; int ess,g[maxn];
void pe(int f,int t){
es[++ess]=(e){t,g[f]}; g[f]=ess; es[++ess]=(e){f,g[t]}; g[t]=ess;
}
struct ask{char opt[3];int x;}; ask asks[maxn];
int n,fa[maxn],p[maxn],q,tag[maxn];
void dfs(int x,int f){for(int i=g[x];i;i=es[i].n)if(es[i].t!=f)fa[es[i].t]=x,dfs(es[i].t,x);}
int find(int x){return x==p[x]?x:p[x]=find(p[x]);}
void uni(int x){int y=find(fa[x]),z=find(x); if(y!=z)p[z]=y;}
int main(){
n=read(); q=read();
inc(i,1,n-1){int a=read(),b=read(); pe(a,b);} dfs(1,0); tag[1]++;
inc(i,1,q){scanf("%s",asks[i].opt); asks[i].x=read(); if(asks[i].opt[0]=='C')tag[asks[i].x]++;}
inc(i,1,n)p[i]=i; inc(i,1,n)if(!tag[i])uni(i);
dec(i,q,1){
if(asks[i].opt[0]=='C'){
tag[asks[i].x]--;
if(!tag[asks[i].x])uni(asks[i].x);
}
if(asks[i].opt[0]=='Q')asks[i].x=find(asks[i].x);
}
inc(i,1,q)if(asks[i].opt[0]=='Q')printf("%d\n",asks[i].x);
return 0;
}给个n点树，每条边的费用为这条边两端的节点数的差值*这条边的长度，求这个数的总费用。
水题，dfs求出节点的子树大小sz，对于每一条边，费用为深度大的sz值与n-sz相减的绝对值乘边的长度。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 1000010
#define ll long long
using namespace std;
struct e{int t,n;}; e es[maxn*2]; int g[maxn],ess;
void pe(int f,int t){
es[++ess]=(e){t,g[f]}; g[f]=ess; es[++ess]=(e){f,g[t]}; g[t]=ess;
}
int f[maxn],t[maxn],sz[maxn],n,dep[maxn]; ll w[maxn],ans;
inline int read(){
char ch=getchar(); int f=1,x=0;
while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return f*x;
}
void dfs(int x,int fa){
sz[x]=1;
for(int i=g[x];i;i=es[i].n)if(es[i].t!=fa)dep[es[i].t]=dep[x]+1,dfs(es[i].t,x),sz[x]+=sz[es[i].t];
}
int main(){
n=read(); inc(i,1,n-1)f[i]=read(),t[i]=read(),w[i]=(ll)read(),pe(f[i],t[i]); dfs(1,0); ll ans=0;
inc(i,1,n-1){
if(dep[f[i]]<dep[t[i]])swap(f[i],t[i]); ans+=(ll)abs(sz[f[i]]-(n-sz[f[i]]))*w[i];
}
printf("%lld",ans); return 0;
}n块土地，现在要求把土地分成几份，每份费用为该份中土地长最大值和宽最大值成绩，要求最小费用。n≤5000
当一块土地长宽都比另一块土地小时，这块土地可以当作另一块土地的附属品，对答案不影响。因此先按长第一关键字，宽第二关键字排序，然后用单调队列就可以把长宽都被覆盖的土地除去。之后剩在单调队列里的土地长是升序排列，宽是降序排列，故用斜率优化dp：f[i]=max(f[j]+长[i]*宽[j+1])，j比k好当且仅当(f[j]-f[k])/(宽[k+1]-宽[j+1])<长[i]。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 50100
#define ll long long
using namespace std;
struct str{ll x,y;}; str strs1[maxn],strs2[maxn];
bool cmp(str a,str b){return a.x!=b.x?a.x<b.x:a.y<b.y;}
inline int read(){
char ch=getchar(); int f=1,x=0;
while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return f*x;
}
int n,l,r,m,q[maxn]; ll f[maxn];
double calc(int j,int k){
return (double)(f[j]-f[k])/(double)(strs2[k+1].y-strs2[j+1].y);
}
int main(){
n=read(); inc(i,1,n)strs1[i].x=(ll)read(),strs1[i].y=(ll)read(); sort(strs1+1,strs1+n+1,cmp); m=0;
inc(i,1,n){while(m&&strs2[m].y<=strs1[i].y)m--; strs2[++m]=strs1[i];} l=1; r=1; q[l]=0;
inc(i,1,m){
while(l<r&&calc(q[l],q[l+1])<strs2[i].x)l++; f[i]=f[q[l]]+strs2[i].x*strs2[q[l]+1].y;
while(l<r&&calc(q[r-1],q[r])>calc(q[r],i))r--; q[++r]=i;
}
printf("%lld",f[m]); return 0;
}n个东西，每个有一个长度Ci。要将这些东西分成几段，每段中东西编号连续。东西编号从i到j的段长度为x=i-j+sigma(k,i,j)Ck,费用为(x-L)^2（L为常量），求最小费用。n≤50000
裸斜率优化dp：\(f[i]=f[j]+((i-j-1)+sum[i]-sum[j]-L)^2\)，j比k好当且仅当\(\frac{f[j]-f[k]+(j+sum[j])^2-(k+sum[k])^2}{j+sum[j]-k-sum[k]}>2*(i+sum[i]-L-1)\)。注意longlong。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 50500
#define ll long long
using namespace std;
inline int read(){
char ch=getchar(); int f=1,x=0;
while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return f*x;
}
int n,l,r,q[maxn]; ll L,sum[maxn],f[maxn];
ll sqr(ll x){return x*x;}
double calc(int j,int k){
return (double)(f[j]-f[k]+sqr(j+sum[j])-sqr(k+sum[k]))/(double)(j+sum[j]-k-sum[k]);
}
int main(){
n=read(); L=(ll)read(); inc(i,1,n){ll a=(ll)read(); sum[i]=sum[i-1]+a;} l=r=1;
inc(i,1,n){
while(l<r&&calc(q[l],q[l+1])<2*(i+sum[i]-L-1))l++;
f[i]=f[q[l]]+sqr((ll)(i-q[l]-1)+sum[i]-sum[q[l]]-L);
while(l<r&&calc(q[r-1],q[r])>calc(q[r],i))r--; q[++r]=i;
}
printf("%lld",f[n]); return 0;
}n个数的序列，m个操作，操作两种：区间开根（向下取整）和区间求和。n≤100000，m≤200000，序列中的数非负且≤10^9。
一个≤109的数开6次根就变成1了。因此开根操作可以暴力只开不是1或0的数。对每个数维护并查集表示离它最近的不是1或0的数，每次只修改这个数在并查集中的根节点，然后跳到根节点的下一个数继续此操作。而数组的快速修改求和用树状数组就可以了。反思：本机测大数据会爆栈，路径压缩得写出非递归形式，但似乎bzoj的栈很大。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 100500
#define ll long long
#define lb(x) x&-x
using namespace std;
inline int read(){
char ch=getchar(); int f=1,x=0;
while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return f*x;
}
int n,m,fa[maxn]; ll c[maxn],v[maxn];
void update(int x,ll val){while(x<=n)c[x]+=val,x+=lb(x);}
ll query(int x){ll q=0; while(x>0)q+=c[x],x-=lb(x); return q;}
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
int main(){
n=read(); inc(i,1,n)v[i]=(ll)read(),fa[i]=i,update(i,v[i]); m=read();
fa[n+1]=n+1; inc(i,1,n)if(v[i]<=1)fa[i]=find(i+1);
inc(i,1,m){
int x=read(),l=read(),r=read();
if(x==1)printf("%lld\n",query(r)-query(l-1));
if(x==2){
int j=l;
while(j<=r){
j=find(j); if(j>r)break; ll y=v[j]; v[j]=(ll)sqrt(y);
update(j,v[j]-y); if(v[j]<=1)fa[j]=find(j+1); j++;
}
}
}
return 0;
}同bzoj3211，但数的大小变为10^12，且操作代码变了。
数组开大，快速读入类型改为longlong即可。（我发现我bzoj3211的代码竟然是错了，wa了好几发，现在已改正）
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 100500
#define ll long long
#define lb(x) x&-x
using namespace std;
inline ll read(){
char ch=getchar(); ll f=1,x=0;
while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return f*x;
}
int n,m,fa[maxn]; ll c[maxn],v[maxn];
void update(int x,ll val){while(x<=n)c[x]+=val,x+=lb(x);}
ll query(int x){ll q=0; while(x>0)q+=c[x],x-=lb(x); return q;}
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
int main(){
n=read(); inc(i,1,n)v[i]=read(),fa[i]=i,update(i,v[i]); m=read();
fa[n+1]=n+1; inc(i,1,n)if(v[i]<=1)fa[i]=find(i+1);
inc(i,1,m){
int x=read(),l=read(),r=read(); if(l>r)swap(l,r);
if(x==1)printf("%lld\n",query(r)-query(l-1));
if(x==0){
int j=l;
while(j<=r){
j=find(j); if(j>r)break; ll y=v[j]; v[j]=(ll)sqrt(y);
update(j,v[j]-y); if(v[j]<=1)fa[j]=find(j+1); j++;
}
}
}
return 0;
}n点m有权边图，每个点都有高度，只能从高度高的点到高度低的点。同时还可以瞬移到走过的点，希望求经过最多点的最短时间。n≤100000，m≤1000000。
第一问：用bfs扩展出能到达的所有点，并标记。第二问：分层做最小生成树。最后一个问题：怎么分层呢？其实很简单，最小生成树之前要把边排序，这个时候我们把高度作为第一关键字，然后高度相同再按照边权排序，这样就分层了啊
感觉很神的样子。反思：因为边数弄错wa了好几发QAQ~
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 100500
#define ll long long
using namespace std;
struct e{int f,t; ll w; int n;}; e es[maxn*20]; int g[maxn],ess,h[maxn];
void pe(int f,int t,ll w){es[++ess]=(e){f,t,w,g[f]}; g[f]=ess;}
bool cmp(e a,e b){return h[a.t]!=h[b.t]?h[a.t]>h[b.t]:a.w<b.w;}
inline int read(){
char ch=getchar(); int f=1,x=0;
while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return f*x;
}
bool vis[maxn]; queue <int> q; int n,m,ans1,fa[maxn],tot; ll ans2;
void bfs(int s){
while(!q.empty())q.pop(); memset(vis,0,sizeof(vis)); q.push(s); vis[s]=1; ans1=1;
while(! q.empty()){
int x=q.front(); q.pop();
for(int i=g[x];i;i=es[i].n)if(!vis[es[i].t])vis[es[i].t]=1,q.push(es[i].t),ans1++;
}
}
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
int main(){
n=read(); m=read(); inc(i,1,n)h[i]=read();
inc(i,1,m){
int a=read(),b=read(); ll c=(ll)read();
if(h[a]>=h[b])pe(a,b,c); if(h[a]<=h[b])pe(b,a,c);
}
bfs(1); sort(es+1,es+ess+1,cmp); inc(i,1,n)fa[i]=i; ans2=tot=0;
inc(i,1,ess){
int x=find(es[i].f),y=find(es[i].t); if(!vis[es[i].f]||!vis[es[i].t]||x==y)continue;
fa[x]=y; tot++; ans2+=es[i].w; if(tot==ans1-1)break;
}
printf("%d %lld\n",ans1,ans2); return 0;
}有n个软件，每个大小为wi，价值为vi，同时每个软件依赖0个或一个其他软件，要求在大小不超过的m的前提下得到最大价值。n≤100，m≤500。
缩点然后做“树上背包dp”，具体看代码，注意里面用到了滚动数组。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define dec(i,j,k) for(int i=j;i>=k;i--)
#define maxn 150
using namespace std;
int bel[maxn],scc,dfn[maxn],low[maxn],tim,st[maxn],top,sv[maxn],sw[maxn],v[maxn],w[maxn]; bool inst[maxn],ok[maxn];
struct e1{int f,t,n;}; e1 es1[maxn*5]; int g1[maxn],ess1;
void pe1(int f,int t){es1[++ess1]=(e1){f,t,g1[f]}; g1[f]=ess1;}
struct e2{int t,n;}; e2 es2[maxn*10]; int g2[maxn],ess2;
void pe2(int f,int t){es2[++ess2]=(e2){t,g2[f]}; g2[f]=ess2; ok[t]=1;}
void init(){
ess1=ess2=0; memset(g1,0,sizeof(g1)); memset(g2,0,sizeof(g2));
tim=scc=0; memset(inst,0,sizeof(inst)); memset(dfn,0,sizeof(dfn));
}
void tarjan(int x){
dfn[x]=low[x]=++tim; st[++top]=x; inst[x]=1;
for(int i=g1[x];i;i=es1[i].n){
if(!dfn[es1[i].t]){
tarjan(es1[i].t); low[x]=min(low[x],low[es1[i].t]);
}else if(inst[es1[i].t])low[x]=min(low[x],dfn[es1[i].t]);
}
if(dfn[x]==low[x]){
scc++; int y=0; while(x!=y)y=st[top],bel[y]=scc,sv[scc]+=v[y],sw[scc]+=w[y],inst[y]=0,top--;
}
}
void build(){inc(i,1,ess1)if(bel[es1[i].f]!=bel[es1[i].t])pe2(bel[es1[i].f],bel[es1[i].t]);}
int f[maxn][maxn*5],n,m;
void dfs(int x){
for(int i=g2[x];i;i=es2[i].n){
dfs(es2[i].t);
dec(j,m-sw[x],0)inc(k,0,j)f[x][j]=max(f[x][j],f[x][k]+f[es2[i].t][j-k]);
}
dec(j,m,0)if(j>=sw[x])f[x][j]=f[x][j-sw[x]]+sv[x];else f[x][j]=0;
}
inline int read(){
char ch=getchar(); int f=1,x=0;
while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return f*x;
}
int main(){
n=read(); m=read(); inc(i,1,n)w[i]=read(); inc(i,1,n)v[i]=read(); init();
inc(i,1,n){int a=read(); if(a)pe1(a,i);} inc(i,1,n)if(!dfn[i])tarjan(i); build();
inc(i,1,scc)if(!ok[i])pe2(scc+1,i); dfs(scc+1); printf("%d",f[scc+1][m]); return 0;
}求一个给定半径的圆圆周上有多少个点的坐标是整数。r≤2*10^9
数学神题，本弱只能转载一下黄学长的题解
首先\(x^2+y^2=r^2\)，变形得\(y^2=(r+x)\times(r-x)\)。令d=gcd(r+x,r-x)，则A=(r-x)/d，B=(r+x)/d，A,B互质，用a,b代入，有\(y^2=d^2\times A\times B\)，由于\(d^2\)，\(y^2\)为完全平方数，故A*B也为完全平方数。又因为A≠B，所以A和B都是完全平方数。设\(a^2=A=(r-x)/d,b^2=B=(r+x)/d\)，则\(a^2+b^2=2r/d\)，因此d为r的约数。 有了上面的推理，那么实现的方法为：枚举d∈[1,sqrt(2R)]，然后根据上述推理可知：必先判d是否为2R的一约数。此时d为2R的约数有两种情况：d=d或d=2R/d。 第一种情况：d=2R/d。枚举a∈[1,sqrt(2R/d/2)] ，算出对应的b=sqrt(2R/d-a^2)，检查是否此时的A,B满足：A≠B且A,B互质，若是就将答案加1 第二种情况：d=d。枚举a∈[1,sqrt(d/2)]，算出对应的b=sqrt(d-a^2)，检查是否此时的A,B满足：A≠B且A,B互质（根据上面的推理可知必需满足此条件），若是就将答案加1 因为这样只算出了第一象限的情况（上面枚举时均是从1开始枚举），根据圆的对称性，其他象限的整点数与第一象限中的整点数相同，最后，在象限轴上的4个整点未算，加上即可，那么最后答案为ans=4*第一象限整点数+4
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#define ll long long
#define inc(i,j,k) for(ll i=j;i<=k;i++)
using namespace std;
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
int main(){
ll n,ans=0; scanf("%lld",&n); n*=2;
inc(i,1,(ll)sqrt(n))if(n%i==0){
ll d=i;
inc(j,1,(ll)sqrt(n/d/2)){
ll b=n/d-j*j; if(sqrt(b)==(double)((ll)sqrt(b))&&gcd(j*j,b)==1&&j*j!=b)ans++;
}
if(d!=n/i){
d=n/i;
inc(j,1,(ll)sqrt(n/d/2)){
ll b=n/d-j*j; if(sqrt(b)==(double)((ll)sqrt(b))&&gcd(j*j,b)==1&&j*j!=b)ans++;
}
}
}
printf("%lld",ans*4+4); return 0;
}给定n维球体上n+1个点的坐标，求球心坐标。n≤10
考虑二维情况，设球心坐标为x,y，第一个坐标为x’，y’，则可得方程\((x-x')^2+(y-y')^2=r^2\)，然后从第二个坐标开始都可以和第一个坐标联立并化简，有了n个方程就可以高斯消元解出球心坐标了，多维情况也很容易推广。反思：第一次写高斯消元。高斯消元的主要思想是将系数矩阵化成倒三角矩阵（满足matrix[i][j],i>j都为0的矩阵)，对于这个矩阵，如果斜线上（即matrix[i][i]）有系数为0且结果矩阵也为0，那么这个元为自由元（可取任何数）；如果斜线上有系数为0且结果矩阵不为0，那么该方程无解；否则该方程有唯一解。高斯消元本来的解法是求出倒三角矩阵后用最后一个方程回代，然而如果一开始就知道解的情况，就可以免回代，在求倒三角矩阵的同时顺便消元。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define maxn 20
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define eps 1e-6
using namespace std;
double a[maxn][maxn],f[maxn]; int n;
double sqr(double x){return x*x;}
bool gauss(){
int now=1,pos; double t;
inc(i,1,n){
for(pos=now;pos<=n;pos++)if(fabs(a[pos][i])>eps)break; if(pos>n)continue;
if(pos!=now){inc(j,1,n+1)swap(a[pos][j],a[now][j]);} t=a[now][i]; inc(j,1,n+1)a[now][j]/=t;
inc(j,1,n)if(j!=now){t=a[j][i]; inc(k,1,n+1)a[j][k]-=t*a[now][k];}
now++;
}
inc(i,now,n)if(fabs(a[i][n+1])>eps)return 0; return 1;
}
int main(){
scanf("%d",&n); inc(i,1,n)scanf("%lf",&f[i]);
inc(i,1,n)inc(j,1,n){double b; scanf("%lf",&b); a[i][j]=2*b-2*f[j]; a[i][n+1]+=sqr(b)-sqr(f[j]);}
gauss();
inc(i,1,n-1)printf("%.3lf ",a[i][n+1]); printf("%.3lf\n",a[n][n+1]);
}n只两种动物，一种有奇数只脚，另一种偶数只角。现在进行m次操作，每次告诉你若干只动物的脚数之和为奇数还是偶数。要求你输出所有动物的类型以及最少多少次操作就能判断。n≤1000，m≤10000
设放进去的动物的系数为1，没放的系数为0，脚数如果是奇数结果就为1，偶数结果为0，解异或方程，具体看代码。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <bitset>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 1010
using namespace std;
bitset <maxn> M[maxn*2]; int n,m,ans; char s[maxn];
void gause(){
int now=0,pos;
inc(i,1,n){
for(pos=now+1;pos<=m&&!M[pos][i];pos++); if(pos==m+1){ans=-1; return;}else ans=max(ans,pos);
now++; swap(M[now],M[pos]); inc(j,1,m)if(j!=now&&M[j][i])M[j]^=M[now];
}
}
int main(){
scanf("%d%d",&n,&m);
inc(i,1,m){scanf("%s",s+1); inc(j,1,n)M[i][j]=s[j]-'0'; int a; scanf("%d",&a); M[i][n+1]=a;}
gause();
if(ans==-1)printf("Cannot Determine");else{
printf("%d\n",ans); inc(i,1,n)printf(M[i][n+1]?"?y7M#\n":"Earth\n");
}
return 0;
}我们称一个由0和1组成的矩阵是和谐的，当且仅当每个元素都有偶数个相邻的1。一个元素相邻的元素包括它本身，及他上下左右的4个元素（如果存在）。给定矩阵的行数和列数，计算并输出一个和谐的矩阵。注意：所有元素为0的矩阵是不允许的。行列数≤40
设矩阵为a，则a[i][j]^a[i+1][j]^a[i-1][j]^a[i][j-1]^a[i][j+1]为0，用i-1替换i则得a[i-1][j]^a[i][j]^a[i-2][j]^a[i-1][j-1]^a[i-1][j+1]=0，每一个元素都与其上面的元素相关，因此可以说第一行的元素决定了所有元素。同时第一行的填法合法当且仅当用第一行推出a[m+1][i]的所有元素都为0。故可以找到a[m+1][j]与第一行哪些元素相关，然后列异或方程组。这个过程可以用二进制弄。如何保证不出现所有元素为0的矩阵出现呢？只要高斯消元时把自由元都当做1就行了，这样一来就必须回代了。反思：二进制操作要用到longlong，然而我强制转换乱写一通导致我wa了n次。尤其是这个地方：M[i][j]=((ll)1<<(j-1)&a[n+1][i])?1:0，我原来是这样写的M[i][j]=((ll)(1<<(j-1)&a[n+1][i])?1:0，这两种解法不同是因为后者先将乘法算出来并溢出了，然后才被转换，而前者不同是因为它把乘数转换了，而longlong*int的结果为longlong故不会溢出，以后要记牢这一点。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <bitset>
#define maxn 50
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define ll long long
using namespace std;
bitset <maxn> M[maxn];
ll a[maxn][maxn];int b[maxn][maxn],n,m;
void gauss(){
int now=0,pos;
inc(i,1,m){
for(pos=now+1;pos<=m&&!M[pos][i];pos++); if(pos>m)continue;
now++; swap(M[pos],M[now]); inc(j,now+1,m)if(M[j][i])M[j]^=M[now];
}
for(int i=m;i>=1;i--){
b[1][i]=M[i][m+1]; if(!M[i][i]){b[1][i]=1; continue;} inc(j,i+1,m)if(M[i][j])b[1][i]^=b[1][j];
}
}
int main(){
scanf("%d%d",&n,&m); inc(i,1,m)a[1][i]=(ll)1<<(i-1);
inc(i,2,n+1)inc(j,1,m)a[i][j]=a[i-2][j]^a[i-1][j-1]^a[i-1][j+1]^a[i-1][j];
inc(i,1,m){inc(j,1,m)M[i][j]=((ll)1<<(j-1)&a[n+1][i])?1:0; M[i][m+1]=0;} gauss();
inc(i,2,n)inc(j,1,m)b[i][j]=b[i-2][j]^b[i-1][j-1]^b[i-1][j+1]^b[i-1][j];
inc(i,1,n){inc(j,1,m-1)printf("%d ",b[i][j]); printf("%d\n",b[i][m]);}
return 0;
}定义f(x)=x的约数个数，求\(\sum_{i=1}^n{f(i)}\)。n≤1000000
只要会思路这道题就很水。对于一个数i，它是n/i个数的约数，对答案有n/i的贡献。所以直接从1枚举到n累加n/i就行了。
#include <cstdio>
using namespace std;
int main(){
int n;scanf("%d",&n); int ans=0;
for(int i=1;i<=n;i++)ans+=n/i;
printf("%d",ans); return 0;
}给定一个字典D，你的程序需要判断若干段文章在字典D下是否能够被理解。 并给出其在字典D下能够被理解的最长前缀的位置。理解定义为这段文章可以拆成字典里的单词。单词数≤10且长度≤10，文章数≤20且长度≤1M。
在trie上跑dp，dp[i]表示文章能否匹配到i这个位置。对于每个i，如果dp[i-1]为1，则从s[i]开始在trie上走，走过的节点数+i的dp值都置为1。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 200
using namespace std;
int ch[maxn][26],n,m,sz; bool d[maxn*10000],val[maxn]; char s[maxn*10000];
void insert(char *s){
int l=strlen(s+1),x=0;
inc(i,1,l){
if(!ch[x][s[i]-'a'])ch[x][s[i]-'a']=++sz; x=ch[x][s[i]-'a'];
}
val[x]=1;
}
int main(){
scanf("%d%d",&n,&m); inc(i,1,n)scanf("%s",s+1),insert(s);
inc(i,1,m){
memset(d,0,sizeof(d)); scanf("%s",s+1); int l=strlen(s+1); d[0]=1;
inc(i,1,l)if(d[i-1]){
int x=0,y=i;
while(s[y]-'a'>=0&&ch[x][s[y]-'a']){
x=ch[x][s[y]-'a']; if(val[x])d[y]=1; y++;
}
}
while(!d[l])l--; printf("%d\n",l);
}
return 0;
}某人读论文，一篇论文是由许多单词组成。但他发现一个单词会在论文中出现很多次，现在想知道每个单词分别在论文中出现多少次。注意论文中单词之间是有分隔的。单词数≤200，长度≤1000000
先将每个单词插入trie，经过的节点的sum[i]++，然后求fail函数，求完后按BFS序倒过来维护sum[fail[i]]+=sum[i]，最后输出第i个单词末尾字符节点的sum值。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 1000010
#define inc(i,j,k) for(int i=j;i<=k;i++)
using namespace std;
int ch[maxn][26],sum[maxn],pos[maxn],q[maxn],n,tot,fail[maxn]; char s[maxn];
int insert(char *s){
int l=strlen(s+1),x=0;
inc(i,1,l){if(!ch[x][s[i]-'a'])ch[x][s[i]-'a']=++tot; x=ch[x][s[i]-'a']; sum[x]++;} return x;
}
void getfail(){
int l=1,r=0; inc(i,0,25)if(ch[0][i])q[++r]=ch[0][i],fail[ch[0][i]]=0;
while(l<=r){
int x=q[l++];
inc(i,0,25)if(ch[x][i]){
int y=fail[x]; while(y&&!ch[y][i])y=fail[y];
if(ch[y][i])fail[ch[x][i]]=ch[y][i]; q[++r]=ch[x][i];
}
}
for(int i=r;i;i--)sum[fail[q[i]]]+=sum[q[i]];
}
int main(){
scanf("%d",&n); tot=0; inc(i,1,n){scanf("%s",s+1); pos[i]=insert(s);}
getfail(); inc(i,1,n)printf("%d\n",sum[pos[i]]);
}维护一个字符串，支持插入，删除，翻转操作。
C++有个库里面有个容器叫rope，可以实现可持久化平衡树，然而本题只要它的插入、删除、截取字符串功能就行了，翻转怎么办？维护一个倒序的rope即可。
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <ext/rope>
#define maxn 2000000
#define inc(i,j,k) for(int i=j;i<=k;i++)
using namespace std;
using namespace __gnu_cxx;
inline int read(){
char ch=getchar(); int f=1,x=0;
while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return f*x;
}
rope <char> l,r,tmp; char ls[maxn],rs[maxn],opt[10]; int n,now;
int main(){
n=read();
inc(i,1,n){
scanf("%s",opt);
if(opt[0]=='M')now=read(); if(opt[0]=='P')now--;
if(opt[0]=='N')now++; if(opt[0]=='G')printf("%c\n",l[now]);
if(opt[0]=='D'){int x=read(),len=l.length(); l.erase(now,x); r.erase(len-now-x,x);}
if(opt[0]=='R'){
int x=read(),len=l.length(); tmp=l.substr(now,x);
l=l.substr(0,now)+r.substr(len-now-x,x)+l.substr(now+x,len-now-x);
r=r.substr(0,len-now-x)+tmp+r.substr(len-now,now);
}
if(opt[0]=='I'){
int x=read(),len=l.length();
inc(i,0,x-1){
ls[i]=getchar(); while(ls[i]<32||ls[i]>126)ls[i]=getchar(); rs[x-i-1]=ls[i];
}
ls[x]=rs[x]=0; l.insert(now,ls); r.insert(len-now,rs);
}
}
}给出一个字典和一个长度，要求有多少个这个长度的字符串里含有子串为字典里的单词。字符串和字典里的字符都为大写字母。单词数≤60，字符串及单词长度≤100。
在AC自动机上跑dp，求不含字典单词的个数，再用总个数减。f[i][j]表示当前处理第i个位置，在trie上的节点为j。f[i][j]=sum{f[i+1][ch[x][k]]}，x为j的fail祖先，为k为大写字母，不能走到val为1的节点。注意val的处理，特别是getfail中的“if(val[ch[y][i]])val[ch[x][i]]=1;”一句。
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
#define maxn 10000
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define mod 10007
using namespace std;
int n,m,sz,ch[maxn][26],fail[maxn],ans,f[150][maxn]; bool val[maxn];
void insert(char *s){
int x=0,len=strlen(s+1); inc(i,1,len){if(!ch[x][s[i]-'A'])ch[x][s[i]-'A']=++sz; x=ch[x][s[i]-'A'];}
val[x]=1;
}
queue <int> q;
void getfail(){
inc(i,0,25)if(ch[0][i])q.push(ch[0][i]),fail[ch[0][i]]=0;
while(!q.empty()){
int x=q.front(); q.pop();
inc(i,0,25)if(ch[x][i]){
int y=fail[x]; while(y&&!ch[y][i])y=fail[y]; if(ch[y][i])fail[ch[x][i]]=ch[y][i];
if(val[ch[y][i]])val[ch[x][i]]=1; q.push(ch[x][i]);
}
}
}
char str[150];
int main(){
scanf("%d%d",&n,&m); inc(i,1,n)scanf("%s",str+1),insert(str); ans=1; getfail();
inc(i,1,m)ans=ans*26%mod; f[0][0]=1;
inc(i,1,m)inc(j,0,sz)if(!val[j]&&f[i-1][j]){
inc(k,0,25){
int x=j; while(x&&!ch[x][k])x=fail[x]; f[i][ch[x][k]]=(f[i][ch[x][k]]+f[i-1][j])%mod;
}
}
inc(i,0,sz)if(!val[i]){
ans=(ans-f[m][i])%mod; if(ans<0)ans+=mod;
}
printf("%d",ans); return 0;
}n点树，m个询问求点u到点v路径上第k小的点权。强制在线。n，m≤100000
用主席树维护某节点到根节点的权值数量sz，建树过程可以由父亲节点递推。询问就用倍增求出lca，然后路径上的sz值就为sz[u]-sz[lca]+sz[v]-sz[fa[lca]]。反思：本弱倍增数组写反了，疯狂reQAQ~
#include <cstdio>
#include <algorithm>
#include <cstring>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 100500
using namespace std;
int f[18][maxn],rt[maxn],dep[maxn],ch[maxn*35][2],sz[maxn*35],v[maxn],id[maxn],n,m,size,last,tot;
struct e{int t,n;}; e es[maxn*2]; int ess,g[maxn];
void pe(int f,int t){es[++ess]=(e){t,g[f]}; g[f]=ess; es[++ess]=(e){f,g[t]}; g[t]=ess;}
struct abc{int v,id;}; abc abcd[maxn]; bool cmp(abc a,abc b){return a.v<b.v;}
inline int read(){
char ch=getchar(); int x=0,f=1;
while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return f*x;
}
void build1(int &x,int l,int r){
x=++size; sz[x]=ch[x][0]=ch[x][1]=0; if(l==r)return;
int mid=(l+r)>>1; build1(ch[x][0],l,mid); build1(ch[x][1],mid+1,r);
}
void insert(int &x,int l,int r,int val){
size++; sz[size]=sz[x]+1; ch[size][0]=ch[x][0]; ch[size][1]=ch[x][1]; x=size; if(l==r)return;
int mid=(l+r)>>1; if(val<=mid)insert(ch[x][0],l,mid,val); if(val>mid)insert(ch[x][1],mid+1,r,val);
}
void dfs(int x,int fa){
rt[x]=rt[fa]; insert(rt[x],1,tot,v[x]);
for(int i=g[x];i;i=es[i].n)if(es[i].t!=fa){
f[0][es[i].t]=x; dep[es[i].t]=dep[x]+1; dfs(es[i].t,x);
}
}
void build2(){
for(int i=1;(1<<i)<=n;i++)inc(j,1,n)f[i][j]=f[i-1][f[i-1][j]];
}
int LCA(int u,int v){
if(dep[u]<dep[v])swap(u,v); int t=dep[u]-dep[v];
for(int i=0;(1<<i)<=n;i++)if(t&(1<<i))u=f[i][u];
for(int i=16;i>=0;i--)if(f[i][u]!=f[i][v])u=f[i][u],v=f[i][v];
return u==v?u:f[0][u];
}
int solve(int u,int v,int k){
int lca=LCA(u,v),l=1,r=tot,x1=rt[v],x2=rt[f[0][lca]],x3=rt[u],x4=rt[lca];
while(l<r){
int mid=(l+r)>>1,tmp=sz[ch[x1][0]]-sz[ch[x2][0]]+sz[ch[x3][0]]-sz[ch[x4][0]];
if(tmp>=k)
r=mid,x1=ch[x1][0],x2=ch[x2][0],x3=ch[x3][0],x4=ch[x4][0];
else
k-=tmp,l=mid+1,x1=ch[x1][1],x2=ch[x2][1],x3=ch[x3][1],x4=ch[x4][1];
}
return l;
}
int main(){
n=read(); m=read(); inc(i,1,n)abcd[i]=(abc){read(),i}; inc(i,1,n-1){int a=read(),b=read(); pe(a,b);}
sort(abcd+1,abcd+1+n,cmp);
inc(i,1,n){if(i==1||abcd[i].v!=abcd[i-1].v)++tot,id[tot]=abcd[i].v; v[abcd[i].id]=tot;}
size=0; build1(rt[0],1,tot); dfs(1,0); build2();
inc(i,1,m){
int u=read()^last,v=read(),k=read(); last=id[solve(u,v,k)]; printf("%d",last); if(i!=m)puts("");
}
return 0;
}n个检查点，在第i个检查点放置塔花费a[i]，放置木偶花费为该位置右边最近一个塔离它的距离。求最小花费。n≤1000000
从右往左处理。在第i个点放塔的费用\(f[i]=\min_j(f[j]+\sum_{k=i+1}^{j-1}{k-i})+a[i]\)，用等差数列求和公式化简后作斜率dp，具体看代码。反思：本弱公式总是推错，要稳！
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
#define maxn 1000010
#define inc(i,j,k) for(int i=j;i<=k;i++)
using namespace std;
int n,q[maxn],l,r; ll c[maxn],f[maxn];
inline int read(){
char ch=getchar(); int x=0,f=1;
while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*f;
}
double calc(int j,int k){
return (double)(2*f[j]-2*f[k]+j-k+(ll)j*j-(ll)k*k)/(double)(j-k);
}
int main(){
n=read(); inc(i,1,n)c[i]=(ll)read(); l=r=0;
inc(i,1,n){
while(l<r&&calc(q[l],q[l+1])<2*i)l++; f[i]=f[q[l]]+((ll)i-q[l])*(i-q[l]-1)/2+c[i];
while(l<r&&calc(q[r-1],q[r])>calc(q[r],i))r--; q[++r]=i;
}
printf("%lld",f[n]);
}维护可以恢复到第k次操作后的并查集。
用可持久化线段树维护并查集的fa数组和秩（在并查集里的深度），不能路径压缩所以用按秩启发式合并，可以使合并均摊复杂度为O(nlog2n)。可持久化线段树实际上就是在更新节点时按主席树的插入方式新建一条路径（其实主席树就是可持久化权值线段树）。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 30000
#define inc(i,j,k) for(int i=j;i<=k;i++)
using namespace std;
int fa[maxn*15],ch[maxn*15][2],dep[maxn*15],pos[maxn*15],sz,n,m,rt[maxn];
inline int read(){
char ch=getchar(); int f=1,x=0;
while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return f*x;
}
void build(int &x,int l,int r){
x=++sz; if(l==r){fa[x]=l; dep[x]=1; pos[x]=l; return;}
int mid=(l+r)>>1; build(ch[x][0],l,mid); build(ch[x][1],mid+1,r);
}
void updatefa(int &x,int l,int r,int a,int b){
sz++; fa[sz]=fa[x]; dep[sz]=dep[x]; pos[sz]=pos[x]; ch[sz][0]=ch[x][0]; ch[sz][1]=ch[x][1];
x=sz; if(l==r){fa[x]=b; return;}
int mid=(l+r)>>1; if(a<=mid)updatefa(ch[x][0],l,mid,a,b);else updatefa(ch[x][1],mid+1,r,a,b);
}
void updatedep(int &x,int l,int r,int a,int b){
sz++; fa[sz]=fa[x]; dep[sz]=dep[x]; pos[sz]=pos[x]; ch[sz][0]=ch[x][0]; ch[sz][1]=ch[x][1];
x=sz; if(l==r){dep[x]=b; return;}
int mid=(l+r)>>1; if(a<=mid)updatedep(ch[x][0],l,mid,a,b);else updatedep(ch[x][1],mid+1,r,a,b);
}
int query(int x,int l,int r,int a){
if(l==r)return x; int mid=(l+r)>>1;
if(a<=mid)return query(ch[x][0],l,mid,a);else return query(ch[x][1],mid+1,r,a);
}
int find(int x,int y){
int z=query(x,1,n,y); if(fa[z]==pos[z])return z;else return find(x,fa[z]);
}
void merge(int &s,int x,int y){
int z1=find(s,x),z2=find(s,y); if(pos[z1]==pos[z2])return; if(dep[z1]>dep[z2])swap(z1,z2);
int abc=max(dep[z2],dep[z1]+1); updatefa(s,1,n,pos[z1],pos[z2]); updatedep(s,1,n,pos[z2],abc);
}
int main(){
n=read(); m=read(); build(rt[0],1,n);
inc(i,1,m){
int opt=read();
if(opt==1){int a=read(),b=read(); rt[i]=rt[i-1]; merge(rt[i],a,b);}
if(opt==2){int k=read(); rt[i]=rt[k];}
if(opt==3){
int a=read(),b=read(); rt[i]=rt[i-1];
if(pos[find(rt[i],a)]==pos[find(rt[i],b)])puts("1");else puts("0");
}
}
return 0;
}同bzoj3673，但强制在线且点数操作数≤200000
T个不停，后来看黄学长博客把数组n*2(log2n)开成结果A了，后来突然明白我fa数组和dep数组是分开维护的，也就是说每次操作新建了两条路径，当然要*2，QAQ~
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 200010
#define inc(i,j,k) for(int i=j;i<=k;i++)
using namespace std;
int fa[maxn*50],ch[maxn*50][2],dep[maxn*50],pos[maxn*50],sz,n,m,rt[maxn];
inline int read(){
char ch=getchar(); int f=1,x=0;
while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return f*x;
}
void build(int &x,int l,int r){
x=++sz; if(l==r){fa[x]=l; dep[x]=1; pos[x]=l; return;}
int mid=(l+r)>>1; build(ch[x][0],l,mid); build(ch[x][1],mid+1,r);
}
void updatefa(int &x,int l,int r,int a,int b){
sz++; fa[sz]=fa[x]; dep[sz]=dep[x]; pos[sz]=pos[x]; ch[sz][0]=ch[x][0]; ch[sz][1]=ch[x][1];
x=sz; if(l==r){fa[x]=b; return;}
int mid=(l+r)>>1; if(a<=mid)updatefa(ch[x][0],l,mid,a,b);else updatefa(ch[x][1],mid+1,r,a,b);
}
void updatedep(int &x,int l,int r,int a,int b){
sz++; fa[sz]=fa[x]; dep[sz]=dep[x]; pos[sz]=pos[x]; ch[sz][0]=ch[x][0]; ch[sz][1]=ch[x][1];
x=sz; if(l==r){dep[x]=b; return;}
int mid=(l+r)>>1; if(a<=mid)updatedep(ch[x][0],l,mid,a,b);else updatedep(ch[x][1],mid+1,r,a,b);
}
int query(int x,int l,int r,int a){
if(l==r)return x; int mid=(l+r)>>1;
if(a<=mid)return query(ch[x][0],l,mid,a);else return query(ch[x][1],mid+1,r,a);
}
int find(int x,int y){
int z=query(x,1,n,y); if(fa[z]==pos[z])return z;else return find(x,fa[z]);
}
void merge(int &s,int x,int y){
int z1=find(s,x),z2=find(s,y); if(pos[z1]==pos[z2])return; if(dep[z1]>dep[z2])swap(z1,z2);
int abc=max(dep[z2],dep[z1]+1); updatefa(s,1,n,pos[z1],pos[z2]); updatedep(s,1,n,pos[z2],abc);
}
int main(){
n=read(); m=read(); build(rt[0],1,n); int last=0;
inc(i,1,m){
int opt=read();
if(opt==1){int a=read()^last,b=read()^last; rt[i]=rt[i-1]; merge(rt[i],a,b);}
if(opt==2){int k=read()^last; rt[i]=rt[k];}
if(opt==3){
int a=read()^last,b=read()^last; rt[i]=rt[i-1];
if(pos[find(rt[i],a)]==pos[find(rt[i],b)])puts("1"),last=1;else puts("0"),last=0;
}
}
return 0;
}一个n（偶数）点图，节点权值为w(v)，边权为c(e)。两人轮流将图中的顶点染色，已经被染过色的点不能再染了，而且每一轮都必须给一个且仅一个顶点染色。染完后每个人的分数为染过的点权和以及两个端点都被染的边权和。如果两人都是采用最优策略的，求最终第一个人的分数减去第二个人的分数。n≤10000，边数≤100000
本弱只能引用神犇的题解
考虑先手选择每个点对答案的影响 一个点如果不选，本身对答案的贡献是-w，一个点如果选，本身对答案的贡献是w，一条边如果两个端点都不选，对答案的贡献是-c，如果两个端点中只选择一个，对答案的贡献是0，如果两个端点都选，对答案的贡献是c，那么我们先预先把所有的权值都在初始答案中减掉，然后就变成了： 一个点如果不选，本身对答案的贡献是0，一个点如果选，本身对答案的贡献是2*w，一条边如果两个端点都不选，对答案的贡献是0，如果两个端点中只选择一个，对答案的贡献是c，如果两个端点都选，对答案的贡献是2*c，那么令一个点的贡献值为本身点权的二倍+所有相连的边的边权，排个序两人轮流取最大即可。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 10010
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define ll long long
using namespace std;
int n,m; ll w[maxn],ans1,ans2;
bool cmp(ll a,ll b){return a>b;}
inline int read(){
char ch=getchar(); int f=1,x=0;
while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return f*x;
}
int main(){
n=read(); m=read(); inc(i,1,n)w[i]=(ll)read()<<1,ans2+=w[i]>>1;
inc(i,1,m){int a=read(),b=read(); ll c=(ll)read(); ans2+=c; w[a]+=c; w[b]+=c;} sort(w+1,w+n+1,cmp);
inc(i,1,n){if(i&1)ans1+=w[i];}
printf("%lld",ans1-ans2); return 0;
}给定一个长度为n的仅包含’B’、‘C’、’S’三种字符的字符串，请找到最长的一段连续子串，使得这一段要么只有一种字符，要么有多种字符，但是没有任意两种字符出现次数相同。
恶心的树状数组题。首先先求出只有一种字符的最长字串。然后预处理出前缀和。题目要求满足
cnt[1][i]-cnt[1][j]!=cnt[2][i]-cnt[2][j] cnt[2][i]-cnt[2][j]!=cnt[3][i]-cnt[3][j] cnt[1][i]-cnt[1][j]!=cnt[3][i]-cnt[3][j]
化简得到cnt[1][i]-cnt[2][i]!=cnt[1][j]-cnt[2][j] cnt[2][i]-cnt[3][i]!=cnt[2][j]-cnt[3][j] cnt[1][i]-cnt[3][i]!=cnt[1][j]-cnt[3][j]
把cnt[1][i]-cnt[2][i],cnt[2][i]-cnt[3][i],cnt[1][i]-cnt[3][i]分别当成xi,yi,zi，题目就转化成对每个i，求一个j使它们的xyz不同且i与j相差最大。首先以x为关键字排序，接着以y（离散化除掉负数，用链表法，如果用排序法会T）为下标建树状数组，树状数组维护6个值：之前处理过的位置的最大最小值、最大最小值对应的z，与最大最小值的z不同的最大最小值。为什么要维护最小值呢？因为按x排序后位置先后顺序会不一样，可能会出现位置靠后的比位置靠前先处理的情况。使x不同的具体方法，就是对于x相同的一组位置，先对它们一起分别查询更新答案，更新答案完后再一起分别插入树状数组。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 1000010
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define lb(x) x&-x
#define INF 0x3fffffff
using namespace std;
struct nd{int id,cnt[3];}; nd nds[maxn]; struct e{int v,n;}; int ess,g[maxn<<1]; e es[maxn];
void pe(int a,int b){es[++ess]=(e){a,g[b]}; g[b]=ess;}
int ans,n,tot; char s[maxn];
struct bit{int mn1,mnz,mn2,mx1,mxz,mx2;}; bit bits1[maxn],bits2[maxn];
bool cmp1(nd a,nd b){return a.cnt[0]<b.cnt[0];}
void query1(nd a){
int b=a.cnt[1]-1;
while(b){
if(bits1[b].mnz==a.cnt[2]){
if(bits1[b].mn2!=INF)ans=max(ans,a.id-bits1[b].mn2);
}else if(bits1[b].mn1!=INF)ans=max(ans,a.id-bits1[b].mn1);
if(bits1[b].mxz==a.cnt[2]){
if(bits1[b].mx2!=0)ans=max(ans,bits1[b].mx2-a.id);
}else if(bits1[b].mx1!=0)ans=max(ans,bits1[b].mx1-a.id);
b-=lb(b);
}
}
void query2(nd a){
int b=a.cnt[1]+1;
while(b<=tot){
if(bits2[b].mnz==a.cnt[2]){
if(bits1[b].mn2!=INF)ans=max(ans,a.id-bits2[b].mn2);
}else if(bits2[b].mn1!=INF)ans=max(ans,a.id-bits2[b].mn1);
if(bits2[b].mxz==a.cnt[2]){
if(bits1[b].mx2!=0)ans=max(ans,bits2[b].mx2-a.id);
}else if(bits2[b].mx1!=0)ans=max(ans,bits2[b].mx1-a.id);
b+=lb(b);
}
}
void update1(nd a){
int b=a.cnt[1];
while(b<=tot){
if(a.id<bits1[b].mn1){
if(a.cnt[2]!=bits1[b].mnz)
bits1[b].mnz=a.cnt[2],bits1[b].mn2=bits1[b].mn1,bits1[b].mn1=a.id;
else bits1[b].mn1=a.id;
}else if(a.cnt[2]!=bits1[b].mnz&&a.id<bits1[b].mn2)bits1[b].mn2=a.id;
if(a.id>bits1[b].mx1){
if(a.cnt[2]!=bits1[b].mxz)
bits1[b].mxz=a.cnt[2],bits1[b].mx2=bits1[b].mx1,bits1[b].mx1=a.id;
else bits1[b].mx1=a.id;
}else if(a.cnt[2]!=bits1[b].mxz&&a.id>bits1[b].mx2)bits1[b].mx2=a.id;
b+=lb(b);
}
}
void update2(nd a){
int b=a.cnt[1];
while(b){
if(a.id<bits2[b].mn1){
if(a.cnt[2]!=bits2[b].mnz)
bits2[b].mnz=a.cnt[2],bits2[b].mn2=bits2[b].mn1,bits2[b].mn1=a.id;
else bits2[b].mn1=a.id;
}else if(a.cnt[2]!=bits2[b].mnz&&a.id<bits2[b].mn2)bits2[b].mn2=a.id;
if(a.id>bits2[b].mx1){
if(a.cnt[2]!=bits2[b].mxz)
bits2[b].mxz=a.cnt[2],bits2[b].mx2=bits2[b].mx1,bits2[b].mx1=a.id;
else bits2[b].mx1=a.id;
}else if(a.cnt[2]!=bits2[b].mxz&&a.id>bits2[b].mx2)bits2[b].mx2=a.id;
b-=lb(b);
}
}
int main(){
scanf("%d",&n); scanf("%s",s+1); int cnt[3]={0,0,0};
int l=1,r=1; while(r<=n){while(r<=n&&s[l]==s[r])ans=max(ans,r-l+1),r++; l++;}
nds[0]=(nd){0,{0,0,0}};
inc(i,1,n){
if(s[i]=='B')cnt[0]++; if(s[i]=='C')cnt[1]++; if(s[i]=='S')cnt[2]++;
nds[i]=(nd){i,{cnt[0]-cnt[1],cnt[0]-cnt[2],cnt[1]-cnt[2]}};
}
ess=0; inc(i,0,n)pe(i,nds[i].cnt[1]+n+1); tot=0;
inc(i,0,n*2+1)if(g[i]){
tot++; int x=g[i]; while(x)nds[es[x].v].cnt[1]=tot,x=es[x].n;
}
inc(i,1,tot)bits1[i]=bits2[i]=(bit){INF,0,INF,0,0,0}; sort(nds,nds+n+1,cmp1); int i=0;
while(i<=n){
int j=i; while(j<=n&&nds[j].cnt[0]==nds[i].cnt[0])j++;
if(i)inc(k,i,j-1){query1(nds[k]); query2(nds[k]);}
inc(k,i,j-1){update1(nds[k]); update2(nds[k]);}
i=j;
}
printf("%d",ans); return 0;
}“X年是自Y年以来降雨量最多的”。它的含义是X年的降雨量不超过Y年，且对于任意Y＜Z＜X，Z年的降雨量严格小于X年。由于有些年份的降雨量未知，有的说法是可能正确也可以不正确的。要求对于一个说法判断它是对、错、有可能。（即使有降雨量未知也有可能可以推出说法错误，具体看题解）信息数≤50000，询问数≤100000
本题坑点非常多。设i年<j年，要分为很多种情况：
具体实现我用的是二分查年份+线段树查最大值。我在二分查询年份位置时没有处理好边界问题导致re了好多发QAQ~
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 100000
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define INF 0x3fffffff
using namespace std;
int x[maxn],y[maxn],mx[maxn*2],n,m,mnn;
inline int read(){
char ch=getchar(); int f=1,x=0;
while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return f*x;
}
void build(int x,int l,int r){
if(l==r){mx[x]=y[l]; return;} int mid=(l+r)>>1;
build(x<<1,l,mid); build(x<<1|1,mid+1,r); mx[x]=max(mx[x<<1],mx[x<<1|1]);
}
int query(int x,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr)return mx[x]; int mid=(l+r)>>1,q=0;
if(ql<=mid)q=max(q,query(x<<1,l,mid,ql,qr)); if(qr>mid)q=max(q,query(x<<1|1,mid+1,r,ql,qr));
return q;
}
int find(int y,bool a){
int l=1,r=n;
if(a){
while(l<r){
int mid=l+((r-l)>>1); if(y<=x[mid])r=mid;else l=mid+1;
}
}else{
while(l<r){
int mid=r-((r-l)>>1); if(y<x[mid])r=mid-1;else l=mid;
}
}
return l;
}
int main(){
n=read(); mnn=INF; inc(i,1,n)x[i]=read(),y[i]=read(),mnn=min(mnn,x[i]);
build(1,1,n); m=read();
inc(i,1,m){
int a=read(),b=read(); int c=find(a,1),d=find(b,1);
if(a>=b){puts("false"); continue;}
if(b!=x[d]){
if(a!=x[c]){puts("maybe"); continue;} if(c==n){puts("maybe"); continue;}
if(query(1,1,n,c+1,find(b,0))>=y[c])puts("false");else puts("maybe"); continue;
}
if(a!=x[c]){
if(d==1){puts("maybe"); continue;}
if(a<mnn){
if(query(1,1,n,1,d-1)>=y[d])puts("false");else puts("maybe");
}else{
if(query(1,1,n,find(a,1),d-1)>=y[d])puts("false");else puts("maybe");
}
continue;
}
if(y[d]>y[c]||query(1,1,n,c+1,d-1)>=y[d])puts("false");else{
if(d-c!=b-a)puts("maybe");else puts("true");
}
}
return 0;
}求0到m的一个数，使它被n次操作后最大。操作三种：&t、|t、^t，t为操作中给定的数。n≤100000，m，t≤1000000000
先求出0经过n次操作后得到的数，然后对于小于等于m的每个二进制位从大到小考虑一下当这位为1时是否比0好，如果好的话令这位为1并让m减去这个二进制位。因为n次操作后为1的二进制位越大越好，所以从大到小考虑是正确的。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 200000
#define inc(i,j,k) for(int i=j;i<=k;i++)
using namespace std;
inline int read(){
char ch=getchar(); int f=1,x=0;
while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return f*x;
}
char s[5]; int opt[maxn],p[maxn],ans,n,m;
int main(){
n=read(); m=read(); ans=0;
inc(i,1,n){
scanf("%s",s); if(s[0]=='A')opt[i]=0; if(s[0]=='O')opt[i]=1; if(s[0]=='X')opt[i]=2; p[i]=read();
}
inc(i,1,n){
if(opt[i]==0)ans&=p[i]; if(opt[i]==1)ans|=p[i]; if(opt[i]==2)ans^=p[i];
}
for(int i=30;i>=0;i--){
int k=1<<i; if(k>m)continue;
inc(j,1,n){
if(opt[j]==0)k&=p[j]; if(opt[j]==1)k|=p[j]; if(opt[j]==2)k^=p[j];
}
if(!(ans&(1<<i))&&(k&(1<<i)))ans|=(1<<i),m-=(1<<i);
}
printf("%d",ans);
}给定一个n×n的棋盘，一个石头被放在棋盘的左上角。他们轮流移动石头。每一回合，选手只能把石头向上，下，左，右四个方向移动一格，并且要求移动到的格子之前不能被访问过。谁不能移动石头了就算输。假如小明先移动石头，而且两个选手都以最优策略走步，问最后谁能赢？
对于n*n为偶数的棋盘肯定可以用二格骨牌覆盖，这样每次先手都是走骨牌的一端而后手就可以走另一端，故后手赢。对于n*n为奇数的棋盘先手走了一步剩下的棋盘就可以被覆盖了，后手面临和之前先手面临的情况一样，故先手赢。由于奇数的平方是奇数，偶数平方是偶数，所以只要对输入判断奇偶性就行了。
#include <cstdio>
int n;
int main(){
while(1){scanf("%d",&n); if(!n)break; puts(n&1?"Bob":"Alice");}
return 0;
}询问一个数组前缀和数组的前缀和，支持单点修改。
\(S_{S_i}=\sum_{i=1}^n{(n-i+1)\times a_i}=(n+1)\times S_i-\sum_{i=1}^n{i\times ai}\)。然后就只要用树状数组维护ai和i*ai的前缀和就行了。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 100010
#define lb(x) x&-x
#define ll long long
using namespace std;
ll v[maxn][2],sm[maxn][2]; int n,m; char s[10];
inline int read(){
char ch=getchar(); int f=1,x=0;
while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return f*x;
}
void update(int x,ll val,bool b){while(x<=n)sm[x][b]+=val,x+=lb(x);}
ll query(int x,bool b){ll q=0; while(x)q+=sm[x][b],x-=lb(x); return q;}
int main(){
n=read(); m=read();
inc(i,1,n)v[i][0]=(ll)read(),v[i][1]=(ll)i*v[i][0],update(i,v[i][0],0),update(i,v[i][1],1);
inc(i,1,m){
scanf("%s",s);
if(s[0]=='Q'){int a=read(); printf("%lld\n",query(a,0)*(a+1)-query(a,1));}
if(s[0]=='M'){
int a=read(); ll b=(ll)read();
update(a,b-v[a][0],0); v[a][0]=b; update(a,b*a-v[a][1],1); v[a][1]=b*a;
}
}
return 0;
}给出一个1到n的全排列，现在对这个全排列序列进行m次局部排序，排序分为两种：1:(0,l,r)表示将区间[l,r]的数字升序排序2:(1,l,r)表示将区间[l,r]的数字降序排序，最后询问第q位置上的数字。
二分最后这个数，判定一个数就是令数组中＞它为1，≤它的为0。然后把排序转成线段树区间赋值，最后查询q位置的数。如果为1则用来判定的数＜答案，如果为0则用来判定的数≥答案。反思：查询区间里有多少个1后，区间赋值时如果查询结果为0，那么区间赋值左端点=r-0+1，右端点=r，则会导致左端点大于右端点，那么就会wa，当查询结果等于区间长度时也会发生类似情况。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 100010
#define inc(i,j,k) for(int i=j;i<=k;i++)
using namespace std;
inline int read(){
char ch=getchar(); int f=1,x=0;
while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return f*x;
}
int n,m,v[maxn],opt[maxn],x[maxn],y[maxn],l,r,k,sm[maxn*5],tag[maxn*5],ll[maxn*5],rr[maxn*5]; bool bit[maxn];
void update(int x){sm[x]=sm[x<<1]+sm[x<<1|1];}
void pushdown(int x){
if(tag[x]!=-1&&ll[x]!=rr[x]){
sm[x<<1]=tag[x]*(rr[x<<1]-ll[x<<1]+1); tag[x<<1]=tag[x];
sm[x<<1|1]=tag[x]*(rr[x<<1|1]-ll[x<<1|1]+1); tag[x<<1|1]=tag[x];
tag[x]=-1;
}
}
void build(int x,int l,int r){
tag[x]=-1; ll[x]=l; rr[x]=r; if(l==r){sm[x]=bit[l]; return;} int mid=(l+r)>>1;
build(x<<1,l,mid); build(x<<1|1,mid+1,r); update(x);
}
void modify(int x,int ql,int qr,bool bit){
if(ql>qr)return; pushdown(x);
if(ql<=ll[x]&&rr[x]<=qr){tag[x]=bit; sm[x]=bit*(rr[x]-ll[x]+1); return;} int mid=(ll[x]+rr[x])>>1;
if(ql<=mid)modify(x<<1,ql,qr,bit); if(mid<qr)modify(x<<1|1,ql,qr,bit); update(x);
}
int query(int x,int ql,int qr){
pushdown(x);
if(ql<=ll[x]&&rr[x]<=qr){return sm[x];} int mid=(ll[x]+rr[x])>>1,q=0;
if(ql<=mid)q+=query(x<<1,ql,qr); if(mid<qr)q+=query(x<<1|1,ql,qr); return q;
}
bool check(int o){
inc(i,1,n)bit[i]=(v[i]>o); build(1,1,n);
inc(i,1,m){
int q=query(1,x[i],y[i]);
if(!opt[i])modify(1,x[i],y[i]-q,0),modify(1,y[i]-q+1,y[i],1);
else modify(1,x[i],x[i]+q-1,1),modify(1,x[i]+q,y[i],0);
}
if(query(1,k,k))return 1;else return 0;
}
int main(){
n=read(); m=read(); inc(i,1,n)v[i]=read(); inc(i,1,m)opt[i]=read(),x[i]=read(),y[i]=read();
k=read(); l=1; r=n;
while(l<r){
int mid=(l+r)>>1; if(check(mid))l=mid+1;else r=mid;
}
printf("%d",l);
}