Kolorowy wąż (kol)
用栈从蛇尾到蛇头记录每一段身体的颜色，每次蛇头变化都认为是新长出了一个蛇头。
对于每个坐标，记录它最后一次是被哪个蛇头经过的，那么根据蛇头版本的差值可以得到对应蛇身相对于蛇头的名次，然后即可在栈中找到对应的颜色。
每次操作的时间复杂度为$O(1)$。
#include<cstdio>
const int N=2005;
int n,m,q,i,j,x,y,z,cnt,len,col[N*N],bean[N][N],last[N][N];char op[9];
inline int ask(int x,int y){
if(x<1||x>n||y<1||y>n)return -1;
int o=last[x][y];
if(!o)return -1;
o=cnt-o+1;
if(o>len)return -1;
return col[len-o+1];
}
int main(){
scanf("%d%d%d",&n,&m,&q);
while(m--)scanf("%d%d%d",&i,&j,&z),bean[i][j]=z+1;
x=y=cnt=len=last[1][1]=1;
while(q--){
scanf("%s",op);
if(op[0]=='Z'){
scanf("%d%d",&i,&j);
printf("%d\n",ask(i,j));
continue;
}
if(op[0]=='G')x--;
else if(op[0]=='D')x++;
else if(op[0]=='L')y--;
else y++;
if(bean[x][y]){
col[++len]=bean[x][y]-1;
bean[x][y]=0;
}
last[x][y]=++cnt;
}
}
Płytkie nawiasowania (ply)
将 '(' 视为$1$，')' 视为$-1$，那么需要满足前缀和介于$[0,k]$，且总和为$0$。
从左往右模拟，一旦在当前位置发现前缀和不在$[0,k]$，就反转当前的括号，一定可以保证代价最小。
时间复杂度$O(n)$。
#include<cstdio>
const int N=1000005;
int n,k,i,s,ans;char a[N];
int main(){
scanf("%d%d%s",&n,&k,a+1);
for(i=1;i<=n;i++){
if(a[i]=='('){
s++;
if(s>k)s-=2,ans++;
}else{
s--;
if(s<0)s+=2,ans++;
}
}
printf("%d",ans);
}
Pociąg towarowy (poc)
找到$pre[i]$表示从左往右贪心匹配出$b[i]$的位置，以及$suf[i]$表示从右往左贪心匹配出$b[i]$的位置。
那么$[pre[i],suf[i]]$中所有值为$b[i]$的位置都可能被匹配，对于$b[i]$这个值出现的所有下标通过差分前缀和打标记即可。
时间复杂度$O(n+m)$。
#include<cstdio>
const int N=300005;
int n,m,k,i,j,a[N],b[N],add[N],del[N],sum[N];
int main(){
scanf("%d%d%d",&n,&m,&k);
for(i=1;i<=n;i++)scanf("%d",&a[i]);
for(i=1;i<=m;i++)scanf("%d",&b[i]);
for(i=j=1;i<=m;i++){
while(a[j]!=b[i])j++;
add[j++]++;
}
for(i=m,j=n;i;i--){
while(a[j]!=b[i])j--;
del[j--]++;
}
for(i=1;i<=n;i++){
j=a[i];
sum[j]+=add[i];
printf("%d%c",!!sum[j],i<n?' ':'\n');
sum[j]-=del[i];
}
}
Wyprzedzanie (wyp)
相邻两辆车一旦紧靠在一起，它们将永远紧靠在一起，可以合并为一辆车。
提取相邻两辆车合并为一个整体的时间点，然后按时间顺序模拟即可，使用链表+堆维护。
实现的时候，需要使用全整数分数类以避免精度误差。
时间复杂度$O(n\log n)$。
#include<cstdio>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
typedef __int128 lll;
typedef pair<int,int>P;
const int N=100005;
int n,i,j,state,pre[N],nxt[N],del[N],ans;
struct Frac{
ll u,d;
Frac(){}
Frac(ll _u,ll _d){u=_u,d=_d;}
void read(){scanf("%lld%lld",&u,&d);}
int sgn(const Frac&b)const{
lll tmp=((lll)u)*((lll)b.d)-((lll)d)*((lll)b.u);
if(!tmp)return 0;
return tmp>0?1:-1;
}
bool operator<(const Frac&b)const{return sgn(b)<0;}
bool operator<=(const Frac&b)const{return sgn(b)<=0;}
}last;
struct Car{
int x,d;
Frac v;
void read(){scanf("%d%d",&x,&d);v.read();}
}car[N];
typedef pair<Frac,P>E;
priority_queue<E,vector<E>,greater<E> >q;
inline void mergeevent(int A,int B){
if(car[A].v<=car[B].v)return;
int delta=car[B].x-car[B].d-car[A].x;
ll u=1LL*delta*car[A].v.d*car[B].v.d,d=car[A].v.u*car[B].v.d-car[A].v.d*car[B].v.u;
q.push(E(Frac(u,d),P(A,B)));
}
inline Frac cal(int B,int o){
if(del[B])return Frac(-1,-1);
int delta=car[B].x;
if(o==0)delta-=car[B].d;else delta+=car[0].d;
ll u=1LL*delta*car[0].v.d*car[B].v.d,d=car[0].v.u*car[B].v.d-car[0].v.d*car[B].v.u;
return Frac(u,d);
}
int main(){
scanf("%d%d",&n,&car[0].d);
car[0].v.read();
for(i=1;i<=n;i++)car[i].read();
for(i=0;i<=n+1;i++){
pre[i]=i-1;
nxt[i]=i+1;
}
for(i=1;i<n;i++)mergeevent(i,i+1);
last=Frac(0,1);
state=1;
for(i=1;i<=n;i++)for(j=0;j<2;j++){
Frac t=cal(i,j);
while(!q.empty()&&t.u>=0){
E e=q.top();
int A=e.second.first,B=e.second.second;
if(del[B]){
q.pop();
continue;
}
if(t<=e.first)break;
last=e.first;
q.pop();
car[B].d+=car[A].d;
del[A]=1;
t=cal(i,j);
int C=pre[A];
pre[B]=C;
nxt[C]=B;
if(C)mergeevent(C,B);
}
if(t.u<0)continue;
if(t<last)continue;
last=t;
if(j==0){
if(state==1)ans++,state=0;
}else{
if(i<n&&cal(nxt[i],0)<t)continue;
state=1;
}
}
printf("%d",ans);
}
Zboże (zbo)
动态点分治。时间复杂度$O(n\log n)$。
#include<cstdio>
typedef long long ll;
const int N=100005,M=2000005;
int n,k,i,x,y,z;
int g[N],v[N<<1],w[N<<1],nxt[N<<1],ok[N<<1],ed;
int son[N],f[N],all,now,cnt;
int G[N],V[2][M],W[M],NXT[M],ED;
int s[N],se[N];ll sd[N],sed[N],ans;
inline void add(int x,int y,int z){v[++ed]=y;w[ed]=z;nxt[ed]=g[x];g[x]=ed;ok[ed]=1;}
inline void ADD(int x,int y,int z,int w){V[0][++ED]=y;V[1][ED]=z;W[ED]=w;NXT[ED]=G[x];G[x]=ED;}
void findroot(int x,int y){
son[x]=1;f[x]=0;
for(int i=g[x];i;i=nxt[i])if(ok[i]&&v[i]!=y){
findroot(v[i],x);
son[x]+=son[v[i]];
if(son[v[i]]>f[x])f[x]=son[v[i]];
}
if(all-son[x]>f[x])f[x]=all-son[x];
if(f[x]<f[now])now=x;
}
void dfs(int x,int y,int dis){
ADD(x,now,cnt,dis);
for(int i=g[x];i;i=nxt[i])if(ok[i]&&v[i]!=y)dfs(v[i],x,dis+w[i]);
}
void solve(int x){
int i;
for(i=g[x];i;i=nxt[i])if(ok[i])cnt++,dfs(v[i],x,w[i]);
for(i=g[x];i;i=nxt[i])if(ok[i]){
ok[i^1]=0;
f[0]=all=son[v[i]];
findroot(v[i],now=0);
solve(now);
}
}
inline void modify(int x){
ans+=sd[x];
s[x]++;
for(int i=G[x];i;i=NXT[i]){
int A=V[0][i],B=V[1][i],C=W[i];
ans+=sd[A]-sed[B]+1LL*C*(s[A]-se[B]);
s[A]++,sd[A]+=C;
se[B]++,sed[B]+=C;
}
}
int main(){
scanf("%d%d",&n,&k);
for(ed=i=1;i<n;i++)scanf("%d%d%d",&x,&y,&z),add(x,y,z),add(y,x,z);
f[0]=all=n;
findroot(1,0);
solve(now);
modify(1);
while(k--)scanf("%d",&x),modify(x),printf("%lld\n",ans*2);
}