模板
#include<bits/stdc++.h>
using namespace std;
const int N=1000002;
int fa[N],dis[N],le[N],ri[N],val[N],x,y,i,n,m;
char c;
inline char gc(){
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int rd(){
int x=0,fl=1;char ch=gc();
for (;ch<48||ch>57;ch=gc())if(ch=='-')fl=-1;
for (;48<=ch&&ch<=57;ch=gc())x=(x<<3)+(x<<1)+(ch^48);
return x*fl;
}
inline void wri(int a){if(a<0)a=-a,putchar('-');if(a>=10)wri(a/10);putchar(a%10|48);}
inline void wln(int a){wri(a);puts("");}
int find(int x){for (;fa[x];x=fa[x]);return x;}
int merge(int u,int v){
if (!u || !v) return u+v;
if (u==v) return u;
if (val[u]>val[v] || val[u]==val[v] && u>v) swap(u,v);
ri[u]=merge(ri[u],v);
fa[ri[u]]=u;
if (dis[le[u]]<dis[ri[u]]) swap(le[u],ri[u]);
dis[u]=dis[ri[u]]+1;
return u;
}
void erase(int u){
fa[le[u]]=fa[ri[u]]=0;val[u]=-1;
merge(le[u],ri[u]);
}
int main(){
n=rd();
for (i=1;i<=n;i++) val[i]=rd();
dis[0]=-1;
for (m=rd();m--;){
do c=gc();while (c!='M' && c!='K');
x=rd();
if (c=='M'){
y=rd();
if (x!=y && val[x]!=-1 && val[y]!=-1) merge(find(x),find(y));
}else{
if (val[x]==-1) puts("0");
else wln(val[x=find(x)]),erase(x);
}
}
}
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1000002;
int v[N],ls[N],rs[N],l[N],r[N],sz[N],d[N],rt[N],i,j,n,p,a[N];
ll ans;
inline char gc(){
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int rd(){
int x=0,fl=1;char ch=gc();
for (;ch<48||ch>57;ch=gc())if(ch=='-')fl=-1;
for (;48<=ch&&ch<=57;ch=gc())x=(x<<3)+(x<<1)+(ch^48);
return x*fl;
}
int merge(int x,int y){
if (!x || !y) return x|y;
if (v[x]<v[y]) swap(x,y);
rs[x]=merge(rs[x],y);
sz[x]=sz[ls[x]]+sz[rs[x]]+1;
if (d[ls[x]]<d[rs[x]]) swap(ls[x],rs[x]);
d[x]=d[rs[x]]+1;
return x;
}
int top(int x){return v[x];}
void pop(int &x){x=merge(ls[x],rs[x]);}
int main(){
n=rd();
for (i=1;i<=n;i++) a[i]=rd()-i;
d[0]=-1;
for (i=1;i<=n;i++){
rt[++p]=i;
sz[i]=1;
v[i]=a[i];
l[p]=r[p]=i;
while (p-1 && top(rt[p])<top(rt[p-1])){
rt[p-1]=merge(rt[p],rt[p-1]);
r[--p]=i;
while (sz[rt[p]]>(r[p]-l[p])/2+1) pop(rt[p]);
}
}
for (i=1;i<=p;i++)
for(j=l[i];j<=r[i];j++) ans+=abs(top(rt[i])-a[j]);
printf("%lld",ans);
}
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1002;
int v[N],ln[N],rn[N],ls[N],rs[N],tot,rt[N],l[N],r[N],d[N],f[N][12],c[N][N],n,K,i,j,k,ans;
int sum(int x){return rs[x]-rn[x]*v[rt[x]]-ls[x]+ln[x]*v[rt[x]];}
int merge(int x,int y){
if (!x || !y) return x+y;
if (v[x]<v[y]) swap(x,y);
r[x]=merge(r[x],y);
if (d[l[x]]<d[r[x]]) swap(l[x],r[x]);
d[x]=d[r[x]]+1;
return x;
}
void solve(){
for (int i=1;i<=n;i++){
ans=tot=0;
for (int j=i;j<=n;j++){
ln[++tot]=1,ls[tot]=v[j];
rt[tot]=j;
l[j]=r[j]=d[j]=rn[tot]=rs[tot]=0;
while (tot>1 && v[rt[tot-1]]>v[rt[tot]]){
ans-=sum(tot-1)+sum(tot);
ln[tot-1]+=ln[tot];
ls[tot-1]+=ls[tot];
rn[tot-1]+=rn[tot];
rs[tot-1]+=rs[tot];
rt[tot-1]=merge(rt[tot-1],rt[tot]);
tot--;
while (ln[tot]>rn[tot]+1){
ln[tot]--,ls[tot]-=v[rt[tot]];
rn[tot]++,rs[tot]+=v[rt[tot]];
rt[tot]=merge(l[rt[tot]],r[rt[tot]]);
}
ans+=sum(tot);
}
c[i][j]=min(c[i][j],ans);
}
}
}
int main(){
while (~scanf("%d%d",&n,&K) && n){
memset(c,63,sizeof(c));
for (i=1;i<=n;i++) scanf("%d",&v[i]),v[i]-=i;
solve();
for (i=1;i<=n;i++) v[i]=-(v[i]+(i<<1));
solve();
memset(f,63,sizeof(f));
f[0][0]=0;
for (i=1;i<=n;i++)
for (j=1;j<=K;j++)
for (k=j-1;k<i;k++) f[i][j]=min(f[i][j],f[k][j-1]+c[k+1][i]);
printf("%d\n",f[n][K]);
}
}
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100002;
int d[N],fa[N],le[N],ri[N],rt[N],i,n,m,w[N],v[N],sz[N];
ll ans,sum[N];
vector<int>vec[N];
inline char gc(){
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int rd(){
int x=0,fl=1;char ch=gc();
for (;ch<48||ch>57;ch=gc())if(ch=='-')fl=-1;
for (;48<=ch&&ch<=57;ch=gc())x=(x<<3)+(x<<1)+(ch^48);
return x*fl;
}
inline void wri(int a){if(a<0)a=-a,putchar('-');if(a>=10)wri(a/10);putchar(a%10|48);}
inline void wln(int a){wri(a);puts("");}
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
int merge(int u,int v){
if (!u || !v) return u+v;
if (u==v) return u;
if (w[u]<w[v]) swap(u,v);
ri[u]=merge(ri[u],v);
fa[ri[u]]=u;
if (d[le[u]]<d[ri[u]]) swap(le[u],ri[u]);
d[u]=d[ri[u]]+1;
return u;
}
void dfs(int u){
sz[u]=1,rt[u]=u,sum[u]=w[u];
for (int i=0,v;i<vec[u].size();i++){
dfs(v=vec[u][i]);
sz[u]+=sz[v];
sum[u]+=sum[v];
rt[u]=merge(rt[u],rt[v]);
}
while (sum[u]>m){
sz[u]--;
sum[u]-=w[rt[u]];
rt[u]=merge(le[rt[u]],ri[rt[u]]);
}
ans=max(ans,1ll*v[u]*sz[u]);
}
int main(){
n=rd(),m=rd();
d[0]=-1;
for (i=1;i<=n;i++) vec[rd()].push_back(i),w[i]=rd(),v[i]=rd();
dfs(1);
printf("%lld",ans);
}
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=300002;
struct node{
int to,ne;
}e[N];
ll val[N],A[N],B[N],h[N],X[N],Y[N];
int die[N],dep[N],i,beg[N],dis[N],end[N],n,m,le[N],ri[N],rt[N],head[N],tot;
inline char gc(){
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline ll rd(){
ll x=0;int fl=1;char ch=gc();
for (;ch<48||ch>57;ch=gc())if(ch=='-')fl=-1;
for (;48<=ch&&ch<=57;ch=gc())x=(x<<3)+(x<<1)+(ch^48);
return x*fl;
}
inline void wri(int a){if(a>=10)wri(a/10);putchar(a%10|48);}
inline void wln(int a){if(a<0)a=-a,putchar('-');wri(a),puts("");}
void add(int x,int y){
e[++tot]=(node){y,head[x]};
head[x]=tot;
}
void get(int u,ll mul,ll pls){
if (!u) return;
val[u]=val[u]*mul+pls;
X[u]*=mul;
Y[u]=Y[u]*mul+pls;
}
void down(int u){
get(le[u],X[u],Y[u]);
get(ri[u],X[u],Y[u]);
X[u]=1,Y[u]=0;
}
int merge(int u,int v){
if (!u || !v) return u+v;
down(u),down(v);
if (val[u]>val[v]) swap(u,v);
ri[u]=merge(ri[u],v);
if (dis[le[u]]<dis[ri[u]]) swap(le[u],ri[u]);
dis[u]=dis[ri[u]]+1;
return u;
}
int erase(int u){return merge(le[u],ri[u]);}
void dfs(int u,int fa){
dep[u]=dep[fa]+1;
for (int i=head[u];i;i=e[i].ne) dfs(e[i].to,u),rt[u]=merge(rt[u],rt[e[i].to]);
while (rt[u] && val[rt[u]]<h[u]){
down(rt[u]);
die[u]++;
end[rt[u]]=u;
rt[u]=erase(rt[u]);
}
get(rt[u],A[u],B[u]);
}
int main(){
n=rd(),m=rd();
for (i=1;i<=n;i++) h[i]=rd();
for (i=2;i<=n;i++){
add(rd(),i);
A[i]=rd(),B[i]=rd();
if (A[i]) A[i]=B[i],B[i]=0;
else A[i]=1;
}
for (i=1;i<=m;i++){
val[i]=rd(),beg[i]=rd();
rt[beg[i]]=merge(rt[beg[i]],i);
X[i]=1;
}
dfs(1,0);
for (i=1;i<=n;i++) wln(die[i]);
for (i=1;i<=m;i++) wln(dep[beg[i]]-dep[end[i]]);
}
#include<bits/stdc++.h>
using namespace std;
const int N=300002;
int fa[N],l[N],r[N],x,y,w[N],add[N],d[N],n,i,m,rx,ry,v;
multiset<int>S;
char s[3];
#define gc getchar
inline int rd(){
int x=0,fl=1;char ch=gc();
for (;ch<48||ch>57;ch=gc())if(ch=='-')fl=-1;
for (;48<=ch&&ch<=57;ch=gc())x=(x<<3)+(x<<1)+(ch^48);
return x*fl;
}
inline void wri(int a){if(a<0)a=-a,putchar('-');if(a>=10)wri(a/10);putchar(a%10|48);}
inline void wln(int a){wri(a),puts("");}
int find(int x){
while (fa[x]) x=fa[x];
return x;
}
void down(int x){
if (add[x]) w[l[x]]+=add[x],w[r[x]]+=add[x],add[l[x]]+=add[x],add[r[x]]+=add[x],add[x]=0;
}
void update(int x){
if (fa[x]) update(fa[x]);
down(x);
}
int merge(int x,int y){
if (!x || !y) return x+y;
down(x),down(y);
if (w[x]<w[y]) swap(x,y);
r[x]=merge(r[x],y);fa[r[x]]=x;
if (d[l[x]]<d[r[x]]) swap(l[x],r[x]);
d[x]=d[r[x]]+1;
return x;
}
int del(int x){
int f=fa[x],t=merge(l[x],r[x]);
fa[x]=l[x]=r[x]=0;
if (x==l[f]) l[f]=t;
else r[f]=t;
fa[t]=f;
return find(t);
}
void erase(int x){S.erase(S.find(x));}
int main(){
n=rd();
for (i=1;i<=n;i++) w[i]=rd(),S.insert(w[i]);
d[0]=-1;
for (m=rd();m--;){
scanf("%s",s);
if (s[0]=='U'){
x=rd(),y=rd();
rx=find(x),ry=find(y);
if (rx==ry) continue;
if (merge(rx,ry)==rx) erase(w[ry]);
else erase(w[rx]);
}
if (s[0]=='A'){
x=rd();
if (s[1]=='1') y=rd(),update(x),erase(w[find(x)]),w[x]+=y,S.insert(w[merge(x,del(x))]);
else if (s[1]=='2') y=rd(),rx=find(x),erase(w[rx]),S.insert(w[rx]+=y),add[rx]+=y;
else v+=x;
}
if (s[0]=='F'){
if (s[1]=='1') x=rd(),update(x),wln(w[x]+v);
else if (s[1]=='2') x=rd(),wln(w[find(x)]+v);
else wln(*(--S.end())+v);
}
}
}
#include<bits/stdc++.h>
using namespace std;
const int N=200002;
int val[N],d[N],le[N],ri[N],LH[N],RH[N],tot,O[N],rt[N],ans,cas,x,y,z,i,fa[N],L[N],R[N],T,n,m;
vector<pair<int,int> >vec;
int init(int x){
val[++tot]=x;
le[tot]=ri[tot]=d[tot]=0;
return tot;
}
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
int merge(int u,int v){
if (!u || !v) return u+v;
if (val[u]>val[v]) swap(u,v);
ri[u]=merge(ri[u],v);
if (d[le[u]]<d[ri[u]]) swap(le[u],ri[u]);
d[u]=d[ri[u]]+1;
return u;
}
int erase(int x){return merge(le[x],ri[x]);}
int insert(int x,int y){return merge(x,init(y));}
void Union(int x,int y){
x=find(x),y=find(y);
if (x==y) return;
fa[y]=x;
if (x<y) RH[x]=RH[y],R[x]=R[y],L[R[x]]=x;
else LH[x]=LH[y],L[x]=L[y],R[L[x]]=x;
rt[x]=merge(rt[x],rt[y]);
O[x]+=O[y];
}
int main(){
for (scanf("%d",&T);T--;){
scanf("%d%d",&n,&m);
memset(rt,0,sizeof(rt));
memset(O,0,sizeof(O));
tot=0;
LH[1]=RH[n]=2e9;
for (i=1;i<n;i++){
scanf("%d",&RH[i]);
LH[i+1]=RH[i];
}
for (i=1;i<=n;i++) L[i]=i-1,R[i]=i+1,fa[i]=i;
vec.clear();
for (ans=0;m--;){
scanf("%d%d%d",&x,&y,&z);
if (z) vec.push_back(make_pair(y+1,x));
else ans++,rt[x]=rt[x]?insert(rt[x],y):init(y);
}
sort(vec.begin(),vec.end());
for (i=0;i<vec.size();i++){
x=find(vec[i].second);
y=vec[i].first;
while (y>LH[x]) Union(x,L[x]),x=find(x);
while (y>RH[x]) Union(x,R[x]),x=find(x);
while (rt[x] && val[rt[x]]<y) rt[x]=erase(rt[x]),O[x]--;
if (++O[x]>=0) ans+=O[x],O[x]=0;
}
printf("Case #%d: %d\n",++cas,ans);
}
}
京公网安备 11010502036488号