【IOI2018】组合动作（构造）
一种思路是：注意到后面的字符都和第一个字符不同，于是对每一位进行2次询问（不用3次，因为剩下的字符可直接确定）确定字符串，不太理想。
但是给询问的字符串长度<=4*n，这启示我们进行并行询问。实际上，假设现在答案字符串为S，先找到首位字符，询问$SAASABSACSB$（A，B，C是除了首位字符的字符）就能知道下一位的结果。（可以看代码）最后一个暴力即可。
但是首位字符需要3次询问，可以二分一下字符集，就可以降到2次询问。
#include <bits/stdc++.h> #include "combo.h" using namespace std; #define p press string guess_sequence(int n) { string r[3], a; if (p("AB")) { if (p("A")) { r[0] = "B"; r[1] = "X"; r[2] = "Y"; a = "A"; } else { r[0] = "A"; r[1] = "X"; r[2] = "Y"; a = "B"; } } else { if (p("X")) { r[0] = "A"; r[1] = "B"; r[2] = "Y"; a = "X"; } else { r[0] = "A"; r[1] = "B"; r[2] = "X"; a = "Y"; } } if(n==1)return a; for (int i = 2; i < n ; i++) { int v = p(a + r[0] + a + r[1] + r[0] + a + r[1] + r[2] + a + r[1] + r[1]); if (v == i+1) a += r[1]; else if (v == i) a += r[0]; else a += r[2]; } if (p(a + r[0])==n) a += r[0]; else if (p(a + r[1])==n) a += r[1]; else a += r[2]; return a; }
代码不合我的码风是因为在loj上格式化了。
【IOI2018】排座位（线段树）
这道题不能用$max-min=r-l$的传统思路。
先考虑$H=1$时怎么做。在线段树上每个叶子节点都维护"把当前值染黑，有多少个黑色连续段"，则答案就是区间最小值个数。（只有0组成的区间显然满足条件，节点的值为1（也是最小值），所以询问区间最小值可以得到正确结果）
把位置相邻的点连边。则每个位置的值是点-边数。
考虑交换操作。由于在区间$[1,l]$和$[r,w]$的节点，这两个点同时被染白/染黑，所以不用计算贡献。如果点在区间$[l,r]$则要计算贡献。可以发现节点的变化情况都是$l$变白，$r$变黑，都是反转颜色。
可以把原来的贡献删除并加入现在的贡献。具体来说，假设一个黑变白的点是$x$旁边是$y$则当$x$是黑的且$y$是白的时候要删除贡献。就是一个区间减法。加入贡献同理。
回到原题，在线段树上每个叶子节点都维护"把当前值染黑，有多少个黑色矩形"，则答案就是区间最小值个数。（只有0组成的区间显然满足条件，节点的值为1）
实际上，这个连续段的个数等于黑点挨着>=2的白点的点个数+白点挨着超过2个黑点的点的个数。
在加入黑点时可以删除原来的贡献并且加入新的贡献。方法类似。
#include<bits/stdc++.h> using namespace std; #define N 4000010 int mn[N],s[N],va[N],bz[N],n,m,mt[N],v,q,ss[N]; #define id(x,y) (x-1)*m+y void bd(int o,int l,int r){ if(l==r){ mn[o]=va[l]; s[o]=1;return; } int md=(l+r)/2; bd(o*2,l,md); bd(o*2+1,md+1,r); mn[o]=min(mn[o*2],mn[o*2+1]); s[o]=0; if(mn[o]==mn[o*2])s[o]+=s[o*2]; if(mn[o]==mn[o*2+1])s[o]+=s[o*2+1]; } void pd(int o){ bz[o*2]+=bz[o]; bz[o*2+1]+=bz[o]; mn[o*2]+=bz[o]; mn[o*2+1]+=bz[o]; bz[o]=0; } void mod(int o,int l,int r,int x,int y,int v){ if(x>y||r<x||y<l)return; if(x<=l&&r<=y){ mn[o]+=v; bz[o]+=v; return; } pd(o); int md=(l+r)/2; mod(o*2,l,md,x,y,v); mod(o*2+1,md+1,r,x,y,v); mn[o]=min(mn[o*2],mn[o*2+1]); s[o]=0; if(mn[o]==mn[o*2])s[o]+=s[o*2]; if(mn[o]==mn[o*2+1])s[o]+=s[o*2+1]; } struct no{ int x,y; }a[N]; int tx[4]={0,-1,0,1},ty[4]={-1,0,1,0}; int in(int x,int y){return x>0&&x<=n&&y>0&&y<=m;} int m1(int x){ int mn=v+1; if(in(tx[0]+a[x].x,ty[0]+a[x].y)) mn=min(mn,mt[id(tx[0]+a[x].x,ty[0]+a[x].y)]); if(in(tx[1]+a[x].x,ty[1]+a[x].y)) mn=min(mn,mt[id(tx[1]+a[x].x,ty[1]+a[x].y)]); return mn; } int m2(int x){ int r1=v+1,r2=v+1; for(int i=0;i<4;i++) if(in(tx[i]+a[x].x,ty[i]+a[x].y)){ if(mt[id(tx[i]+a[x].x,ty[i]+a[x].y)]<r1) r2=r1,r1=mt[id(tx[i]+a[x].x,ty[i]+a[x].y)]; else if(mt[id(tx[i]+a[x].x,ty[i]+a[x].y)]<r2) r2=mt[id(tx[i]+a[x].x,ty[i]+a[x].y)]; } return r2; } int main(){ scanf("%d%d%d",&n,&m,&q); v=n*m; for(int i=1;i<=v;i++){ scanf("%d%d",&a[i].x,&a[i].y); a[i].x++; a[i].y++; mt[id(a[i].x,a[i].y)]=i; } for(int i=1;i<=v;i++){ va[i]=va[i-1]; if(m2(i)<i)va[i]--; if(m1(i)>i)va[i]++; for(int j=0;j<4;j++) if(in(tx[j]+a[i].x,ty[j]+a[i].y)){ int v=mt[id(tx[j]+a[i].x,ty[j]+a[i].y)]; if(v<i&&m1(v)==i)va[i]--; else if(v>i&&m2(v)==i)va[i]++; } } bd(1,1,v); while(q--){ int x,y,ct=0; scanf("%d%d",&x,&y); x++; y++; if(x>y)swap(x,y); if(x==y){ printf("%d",s[1]); printf(" "); continue; } ss[++ct]=x;ss[++ct]=y; for(int i=0;i<4;i++) if(in(tx[i]+a[x].x,ty[i]+a[x].y)) ss[++ct]=mt[id(tx[i]+a[x].x,ty[i]+a[x].y)]; for(int i=0;i<4;i++) if(in(tx[i]+a[y].x,ty[i]+a[y].y)) ss[++ct]=mt[id(tx[i]+a[y].x,ty[i]+a[y].y)]; sort(ss+1,ss+ct+1); for(int i=1;i<=ct;i++) if(ss[i]!=ss[i-1]){ if(m2(ss[i])<ss[i]) mod(1,1,v,max(m2(ss[i]),x),min(ss[i],y)-1,-1); if(m1(ss[i])>ss[i]) mod(1,1,v,max(ss[i],x),min(m1(ss[i]),y)-1,-1); } swap(mt[id(a[x].x,a[x].y)],mt[id(a[y].x,a[y].y)]); swap(a[x],a[y]); for(int i=1;i<=ct;i++) if(ss[i]!=ss[i-1]){ if(m2(ss[i])<ss[i]) mod(1,1,v,max(m2(ss[i]),x),min(ss[i],y)-1,1); if(m1(ss[i])>ss[i]) mod(1,1,v,max(ss[i],x),min(m1(ss[i]),y)-1,1); } printf("%d",s[1]); printf(" "); } }
【IOI2018】狼人（可持久化线段树，Kruskal重构树，dfs序）
由于在人形态不能经过$<l$的点，所以经过的点的标号最小值要$geq l$。可以考虑建出边权为$max(x,y)$（x,y为边的两端点标号）的kruskal重构树。
同理可以建出边权为$min(x,y)$（x,y为边的两端点标号）的kruskal重构树。
在判定是否能变身时，可以在重构树上dfs一下得到dfs序，把所有点视为平面上的一个点$(dfn1_x,dfn2_x)$，则查询时倍增到对应的点，则倍增到的位置的子树的所有节点是当前点可以走的。判定是否有点在这2个区间构成的矩形即可。数点可用离线+BIT/可持久化线段树解决
#include<bits/stdc++.h> using namespace std; #define N 800010 int n,m,q,rt[N],lc[N<<4],rc[N<<4],sz[N<<4],ct,va[N]; struct ed{ int a,b,c; }e[N]; int operator <(ed x,ed y){return x.c<y.c;} int cp(ed x,ed y){return x.c>y.c;} void mod(int &o,int p,int l,int r,int x){ if(!o)o=++ct; sz[o]=sz[p]+1; if(l==r)return; int md=(l+r)/2; if(x<=md){ rc[o]=rc[p]; mod(lc[o],lc[p],l,md,x); } else{ lc[o]=lc[p]; mod(rc[o],rc[p],md+1,r,x); } } int qu(int o,int p,int l,int r,int x,int y){ if(!o||r<x||y<l)return 0; if(x<=l&&r<=y)return sz[o]-sz[p]; int md=(l+r)/2; return qu(lc[o],lc[p],l,md,x,y)+qu(rc[o],rc[p],md+1,r,x,y); } struct no{ int f[N][20],p[N],ct,a[N],ec,dfn[N],cc,v[N*2],nxt[N*2],h[N],rt,d1[N],d2[N]; ed d[N]; void add(int x,int y){v[++ec]=y;nxt[ec]=h[x];h[x]=ec;} int fd(int x){return p[x]?p[x]=fd(p[x]):x;} void bd(){ ct=n; for(int i=1;i<=n;i++)a[i]=i; for(int i=1;i<=m;i++){ int xx=fd(d[i].a),yy=fd(d[i].b); if(xx!=yy){ ct++; a[ct]=d[i].c; f[xx][0]=ct; f[yy][0]=ct; p[xx]=p[yy]=ct; add(ct,xx); add(ct,yy); rt=ct; } } for(int i=1;i<20;i++) for(int j=1;j<=ct;j++) f[j][i]=f[f[j][i-1]][i-1]; } void dfs(int x,int t){ if(x<=n)dfn[x]=++cc; for(int i=h[x];i;i=nxt[i]) dfs(v[i],t); if(x>n)d1[x]=1e9; else d2[x]=d1[x]=dfn[x]; for(int i=h[x];i;i=nxt[i]){ d2[x]=max(d2[x],d2[v[i]]); d1[x]=min(d1[x],d1[v[i]]); } } void init(int t){ if(t){ for(int i=1;i<=m;i++){ d[i]=e[i]; d[i].c=min(e[i].a,e[i].b); } sort(d+1,d+m+1,cp); } else{ for(int i=1;i<=m;i++){ d[i]=e[i]; d[i].c=max(e[i].a,e[i].b); } sort(d+1,d+m+1); } bd(); dfs(rt,t); } int bz(int x,int t,int v){ for(int i=19;~i;i--){ if(t&&a[f[x][i]]>=v&&f[x][i])x=f[x][i]; else if(!t&&a[f[x][i]]<=v&&f[x][i])x=f[x][i]; } return x; } }x,y; int main(){ cin>>n>>m>>q; for(int i=1;i<=m;i++){ scanf("%d%d",&e[i].a,&e[i].b); e[i].a++; e[i].b++; } x.init(1); y.init(0); for(int i=1;i<=n;i++) va[x.dfn[i]]=i; for(int i=1;i<=n;i++) mod(rt[i],rt[i-1],1,y.cc,y.dfn[va[i]]); while(q--){ int a,b,c,d; scanf("%d%d%d%d",&a,&b,&c,&d); a++;b++;c++;d++; int p1=x.bz(a,1,c),p2=y.bz(b,0,d); int l1=x.d1[p1],r1=x.d2[p1]; int l2=y.d1[p2],r2=y.d2[p2]; if(qu(rt[r1],rt[l1-1],1,n,l2,r2))puts("1"); else puts("0"); } }
【IOI2018】机械娃娃（线段树，构造）
题目中给了$2$-开关，可以考虑把它扩展到$k$-开关
可以使用线段树构造。构造一颗线段树，大小为$m$（m为最小的$2$的次幂使其>=关键点个数）。叶子节点连向对应的关键点，如果一个点没有连向关键点（叶子节点超出需求），就把它连向根。这样子最坏情况要$2*n$个开关，不太理想。
注意到，如果一个点子树的所有叶子节点都被连到根，则可以把这个子树除当前节点的其他节点删除，并且把当前点连向根。但是由于访问到的顺序是fft的rev数组，复杂度没有保证，连的效果不好。
实际上，可以把线段树的右边n-关键点个节点空出来，类似区间定位一样找到$log_2 n$个节点，把它们的子树都删掉，把这$log_2 n$个节点都连到根。
没被空出来的节点按顺序连到关键点即可。这样子就可以把开关数降到$n+log_2 n$
#include<bits/stdc++.h> #include "doll.h" using namespace std; #define N 300010 vector<int>c,x,y; int n,p=1,l,rv[N],tv[N],tp[N]; int bd(int l,int r){ if(l==r)return l>=p-n?tv[l]:-p; int md=(l+r)/2; int lc=bd(l,md),rc=bd(md+1,r); if(lc==-p&&rc==-p)return -p; x.push_back(lc); y.push_back(rc); return -x.size(); } void create_circuit(int m,vector<int>v){ n=v.size(); v.push_back(0); while(p<=n)p*=2,l++; for(int i=0;i<p;i++) rv[i]=(rv[i>>1]>>1)|((i&1)<<(l-1)); memset(tp,127,sizeof(tp)); for(int i=p-n;i<p;i++)tp[rv[i]]=i; int ct=0; for(int i=0;i<p;i++) if(tp[i]<2e9)tv[tp[i]]=v[++ct]; int rt=bd(0,p-1); c.push_back(v[0]); for(int i=0;i<m;i++) c.push_back(rt); for(auto &i:x)if(i==-p)i=rt; for(auto &i:y)if(i==-p)i=rt; answer(c,x,y); }
【IOI2018】高速公路收费（二分，最短路）
先询问一下得到原图的最短路。
考虑在图上二分出一条最短路的边。（不能二分出点，否则只能拿最多$90$分。如果二分出点拿到$100$分请告诉笔者。）
二分的方法是：（下文设md为区间终点）把左端点$l$到$md$的边设为拥堵边，检测询问的值是否等于原图的最短路。如果是则右移左端点否则左移右端点。
如果把$[l,md]$设为拥堵边后询问的值不是最短路，则所有最短路上的边都在$[l,md]$里面。
如果把$[l,md]$设为拥堵边后询问的值是最短路，则不是所有最短路的边都在$[l,md]$中。
（咕咕咕）
代码不合我的码风是因为在loj上格式化了。
【IOI2018】会议（线段树，dp）
由题意可以得到一个dp方程：设$f_{l,r}$表示$[l,r]$区间最小代价，由题意$f_{l,r}=min(f_{l,md-1}+(r-md+1)*h_{md},f_{md+1,r}+(md-l+1)*h_{md})$，其中$md$为最小值所在位置。
但是这样子效率太低。只能过$19$分。不能直接把$dp$数组计算出来，而要根据询问减少计算量。
根据套路考虑建出原序列的笛卡尔树，可以用rmq建，然后把每一个询问挂在笛卡尔树对应的点上。这样子的好处是每次处理的$mid$都是一定的。
对于询问$[l,r]$只和$f_{l,md-1}$和$f_{md+1,r}$有关。且这2个dp数组有一个端点是$md-1$或$md+1$。对于下面的子任务，笛卡尔树不高，所以可以暴力算。这样子可以拿到$60$分。
所以可以考虑用线段树维护$f_{l...md-1,md-1}$和$f_{md+1...r,r}$的值（$l,r$是当前分治区间不是询问区间），对于每一个询问单点询问就可以直接得到答案。
考虑做完当前点后维护$f_{l...r,r}$和$f_{l,l...r}$的值。考虑计算$f_{l...r,r}$的值的过程。可以观察原dp方程，可以注意到当$r$向右移一位时，左边的项会增加$h_{md}$，右边的项会增加$f_{md+1,r}-f_{md+1,r-1}$。一边的贡献是一次函数，但是可以不用李超树维护。由于笛卡尔树的性质，区间$[md+1,r]$的最小值小于等于$md$的最小值。所以右边的增量$leq md$。所以方程取左边还是右边有一个分界线，可以二分出这个分界线然后更新线段树（就是区间一次函数覆盖/区间加）。（其实不用二分。只要维护线段树左/右端点处的值，当左边比右边端点取方程同一边时直接改，否则继续递归）。
然后上传到上面的区间。这样子上传没有问题。先讨论一下以当前右端点为$r$的dp数组（左端点为$l$的数组相似），是因为如果新的最大值位置是$r+1$，则现在更新的dp值恰好可以用于更新上面的询问。如果新的最大值位置为$l-1$，则不用更新上面的询问。由于笛卡尔树上当前点的子节点已经被算完了，所以不会对当前点的子节点产生影响。
自此，我们在$O(nlog_2 n)$的时间内离线解决了这道题。如果硬要在线只要把线段树可持久化一下即可。
#include<bits/stdc++.h> using namespace std; typedef long long ll; #define N 750010 struct st{ ll ck[N<<2],cb[N<<2],ad[N<<2],vl[N<<2],vr[N<<2],cc[N<<2]; void cv(int o,int l,int r,ll k,ll b){ cc[o]=1; ad[o]=0; vl[o]=k*l+b; vr[o]=k*r+b; ck[o]=k; cb[o]=b; } void av(int o,ll v){ ad[o]+=v; vl[o]+=v; vr[o]+=v; } void pd(int o,int l,int r){ int md=(l+r)/2; if(cc[o]){ cv(o*2,l,md,ck[o],cb[o]); cv(o*2+1,md+1,r,ck[o],cb[o]); cc[o]=0; } if(ad[o]){ av(o*2,ad[o]); av(o*2+1,ad[o]); ad[o]=0; } } ll q(int o,int l,int r,int x){ if(l==r)return vl[o]; int md=(l+r)/2; pd(o,l,r); ll rr=(x<=md)?q(o*2,l,md,x):q(o*2+1,md+1,r,x); return rr; } void mod(int o,int l,int r,int x,int y,ll k,ll b,ll v){ if(r<x||y<l)return; if(x<=l&&r<=y){ if(k*r+b<=vr[o]+v&&k*l+b<=vl[o]+v){ cv(o,l,r,k,b); return; } if(k*r+b>=vr[o]+v&&k*l+b>=vl[o]+v){ av(o,v); return; } } pd(o,l,r); int md=(l+r)/2; mod(o*2,l,md,x,y,k,b,v); mod(o*2+1,md+1,r,x,y,k,b,v); vl[o]=vl[o*2]; vr[o]=vr[o*2+1]; } }fl,fr; int n,q,lg[N],f[N][20],l[N],r[N]; vector<int>v[N]; ll a[N],h[N]; int mm(int x,int y){ return h[x]>h[y]?x:y; } int qu(int l,int r){ int v=lg[r-l+1]; return mm(f[l][v],f[r-(1<<v)+1][v]); } void dfs(ll x,ll y){ if(x>y)return; ll md=qu(x,y); ll l1=0,r1=0; dfs(x,md-1);dfs(md+1,y); for(auto i:v[md]){ a[i]=(ll)h[md]*(r[i]-l[i]+1); if(l[i]<md)a[i]=min(a[i],(ll)(r[i]-md+1)*h[md]+fr.q(1,1,n,l[i])); if(r[i]>md)a[i]=min(a[i],(ll)(md-l[i]+1)*h[md]+fl.q(1,1,n,r[i])); } if(x<md)l1=fr.q(1,1,n,x); if(y>md)r1=fl.q(1,1,n,y); fr.mod(1,1,n,x,md,-h[md],r1+(ll)h[md]*(md+1),(ll)h[md]*(y-md+1)); fl.mod(1,1,n,md,y,h[md],l1-(ll)h[md]*(md-1),(ll)h[md]*(md-x+1)); } int main(){ scanf("%d%d",&n,&q); for(int i=1;i<=n;i++) scanf("%d",&h[i]); for(int i=2;i<N;i++) lg[i]=lg[i>>1]+1; for(int i=1;i<=n;i++) f[i][0]=i; for(int i=1;i<20;i++) for(int j=1;j+(1<<(i))-1<=n;j++) f[j][i]=mm(f[j][i-1],f[j+(1<<(i-1))][i-1]); for(int i=1;i<=q;i++){ scanf("%d%d",&l[i],&r[i]); l[i]++;r[i]++; int md=qu(l[i],r[i]); v[md].push_back(i); } dfs(1,n); for(int i=1;i<=q;i++) printf("%lld ",a[i]); }