单调队列
#include<bits/stdc++.h> #define N 1000007 using namespace std; int n,k,l,r,x,cnt1,cnt2; int q[N],a[N]; inline int read() { int x=0,f=1;char c=getchar(); while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } int main() { n=read();k=read(); for(int i=1;i<=n;i++) a[i]=read(); l=1,r=1; for(int i=1;i<=n;i++) { while(l<r && a[q[r-1]]>a[i]) r--; q[r++]=i; while(l<r && q[l]<=i-k) l++; if(i>=k) printf("%d ",a[q[l]]); }printf(" "); memset(q,0,sizeof q); l=1;r=1; for(int i=1;i<=n;i++) { while(l<r && a[q[r-1]]<a[i]) r--; q[r++]=i; while(l<r && q[l]<=i-k) l++; if(i>=k) printf("%d ",a[q[l]]); }printf(" "); return 0; }
线段树
/* codevs1082 */ #include<iostream> #include<cstdio> #include<cstring> #define N 200001 #define ll long long using namespace std; ll n,m,x,y,z,opt; struct tree{ ll l,r,sum,flag; }tr[N<<2]; inline ll read() { ll x=0,f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } inline void pushup(int k) { tr[k].sum=tr[k<<1].sum+tr[k<<1|1].sum; } inline void pushdown(int k) { tr[k<<1].flag+=tr[k].flag; tr[k<<1].sum+=(tr[k<<1].r-tr[k<<1].l+1)*tr[k].flag; tr[k<<1|1].flag+=tr[k].flag; tr[k<<1|1].sum+=(tr[k<<1|1].r-tr[k<<1|1].l+1)*tr[k].flag; tr[k].flag=0; } void build(int k,int l,int r) { tr[k].l=l;tr[k].r=r;tr[k].sum=0; if(l==r) { tr[k].sum=read(); return; } int mid=l+r>>1; build(k<<1,l,mid);build(k<<1|1,mid+1,r); pushup(k); } void change(int k,int l,int r,int del) { if(tr[k].l==l && tr[k].r==r) { tr[k].sum+=(r-l+1)*del; tr[k].flag+=del; return; } if(tr[k].flag) pushdown(k); int mid=tr[k].l+tr[k].r>>1; if(r<=mid) change(k<<1,l,r,del); else if(l>mid) change(k<<1|1,l,r,del); else change(k<<1,l,mid,del),change(k<<1|1,mid+1,r,del); pushup(k); } ll query(int k,int l,int r) { if(tr[k].l==l && tr[k].r==r) return tr[k].sum; if(tr[k].flag) pushdown(k); pushup(k); int mid=tr[k].l+tr[k].r>>1; if(r<=mid) return query(k<<1,l,r); else if(l>mid) return query(k<<1|1,l,r); else return query(k<<1,l,mid)+query(k<<1|1,mid+1,r); } int main() { n=read(); build(1,1,(int)n); m=read(); for(int i=1;i<=m;i++) { opt=read(); if(opt==1) { x=read(),y=read(),z=read(); change(1,(int)x,(int)y,(int)z); } else { x=read(),y=read(); printf("%lld ",query(1,(int)x,(int)y)); } } return 0; }
/* codevs1228 */ #include<iostream> #include<cstdio> #include<cstring> #define N 100007 using namespace std; int n,m,k,ans,cnt,num; int head[N],S[N],T[N],Q[N]; struct tree{ int l,r,sum,flag; }tr[N<<2]; struct node{ int v,net; }e[N<<1]; inline int read() { int x=0,f=1;char c=getchar(); while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } inline void add(int u,int v) { e[++cnt].v=v;e[cnt].net=head[u];head[u]=cnt; } inline void pushup(int k) { tr[k].sum=tr[k<<1].sum+tr[k<<1|1].sum; } void dfs(int u,int fa) { S[u]=++cnt; for(int i=head[u];i;i=e[i].net) { int v=e[i].v; if(v==fa) continue; dfs(v,u); }T[u]=cnt; } void build(int k,int l,int r) { tr[k].l=l;tr[k].r=r; if(l==r){tr[k].sum=1;return;} int mid=l+r>>1; build(k<<1,l,mid);build(k<<1|1,mid+1,r); pushup(k); } void change(int k,int pos) { if(tr[k].l==tr[k].r && tr[k].l==pos) { tr[k].sum^=1; return; } int mid=tr[k].l+tr[k].r>>1; if(pos<=mid) change(k<<1,pos); if(pos>mid) change(k<<1|1,pos); pushup(k); } int query(int k,int l,int r) { if(tr[k].l==l && tr[k].r==r) return tr[k].sum; int mid=(tr[k].l+tr[k].r)>>1; pushup(k); if(l>mid) return query(k<<1|1,l,r); else if(r<=mid) return query(k<<1,l,r); else return query(k<<1,l,mid)+query(k<<1|1,mid+1,r); } int main() { int x,y;char ch; n=read(); for(int i=1;i<n;i++) { x=read();y=read(); add(x,y);add(y,x); }cnt=0; dfs(1,0);build(1,1,n);m=read(); for(int i=1;i<=m;i++) { cin>>ch;x=read(); if(ch=='C') change(1,S[x]); else printf("%d ",query(1,S[x],T[x])); } return 0; }
/* bzoj1798 */ #include<iostream> #include<cstdio> #include<cstring> #define ll long long #define N 100010 using namespace std; ll ans,mod; int n,m; struct tree { int l,r; ll mul_,sum_; ll sum; }tr[N<<3]; void pushup(int k) { tr[k].sum=(tr[k<<1].sum+tr[k<<1|1].sum)%mod; } void build(int k,int l,int r) { tr[k].l=l;tr[k].r=r;tr[k].sum_=0;tr[k].mul_=1; if(l==r) { scanf("%lld",&tr[k].sum); return; } int mid=(l+r)>>1; build(k<<1,l,mid);build(k<<1|1,mid+1,r); pushup(k); } void down_sum(int k) { tr[k<<1].sum_=(tr[k].sum_+tr[k<<1].sum_)%mod; tr[k<<1].sum =(tr[k<<1].sum + (tr[k<<1].r-tr[k<<1].l+1)*tr[k].sum_)%mod; tr[k<<1|1].sum_=(tr[k].sum_+tr[k<<1|1].sum_)%mod; tr[k<<1|1].sum =(tr[k<<1|1].sum + (tr[k<<1|1].r-tr[k<<1|1].l+1)*tr[k].sum_)%mod; tr[k].sum_=0; } void down_mul(int k) { tr[k<<1].sum =(tr[k<<1].sum *tr[k].mul_)%mod; tr[k<<1].sum_=(tr[k<<1].sum_*tr[k].mul_)%mod; tr[k<<1].mul_=(tr[k<<1].mul_*tr[k].mul_)%mod; tr[k<<1|1].sum =(tr[k<<1|1].sum *tr[k].mul_)%mod; tr[k<<1|1].sum_=(tr[k<<1|1].sum_*tr[k].mul_)%mod; tr[k<<1|1].mul_=(tr[k<<1|1].mul_*tr[k].mul_)%mod; tr[k].mul_=1; } void changesum(int k,int l,int r,int c) { if(l>r||r<l) return; if(tr[k].l==l && tr[k].r==r) { tr[k].sum_=(tr[k].sum_+c)%mod; tr[k].sum=(tr[k].sum+(tr[k].r-tr[k].l+1)*c)%mod; return; } if(tr[k].mul_!=1) down_mul(k); if(tr[k].sum_) down_sum(k); int mid=(tr[k].l+tr[k].r)>>1; if(r<=mid) changesum(k<<1,l,r,c); else if(l>mid) changesum(k<<1|1,l,r,c); else changesum(k<<1,l,mid,c),changesum(k<<1|1,mid+1,r,c); pushup(k); } void changemul(int k,int l,int r,int c) { if(l>r||r<l) return; if(tr[k].l==l && tr[k].r==r) { tr[k].mul_=(tr[k].mul_*c)%mod; tr[k].sum_=(tr[k].sum_*c)%mod; tr[k].sum=(tr[k].sum*c)%mod; return; } if(tr[k].mul_!=1) down_mul(k); if(tr[k].sum_) down_sum(k); int mid=(tr[k].l+tr[k].r)>>1; if(r<=mid) changemul(k<<1,l,r,c); else if(l>mid) changemul(k<<1|1,l,r,c); else changemul(k<<1,l,mid,c),changemul(k<<1|1,mid+1,r,c); pushup(k); } int query(int k,int l,int r) { if(l>r||r<l) return 0; if(tr[k].l==l && tr[k].r==r) return tr[k].sum%mod; if(tr[k].mul_!=1) down_mul(k); if(tr[k].sum_) down_sum(k); pushup(k); int mid=(tr[k].r+tr[k].l)>>1; if(r<=mid) return query(k<<1,l,r)%mod; else if(l>mid) return query(k<<1|1,l,r)%mod; else return query(k<<1,l,mid)%mod+query(k<<1|1,mid+1,r)%mod; } int main() { scanf("%d%lld",&n,&mod); build(1,1,n); scanf("%d",&m); int f, x, y; long long c; for(int i=1;i<=m;i++) { scanf("%d",&f); if(f==1) { scanf("%d%d%lld",&x,&y,&c); changemul(1,x,y,c); } else if(f==2) { scanf("%d%d%lld",&x,&y,&c); changesum(1,x,y,c); } else { scanf("%d%d",&x,&y); printf("%lld ",query(1,x,y)%mod); } } return 0; }
ST表
/* P3865 */ #include<iostream> #include<cstdio> #include<cstring> #define N 100007 using namespace std; int n,m,k,ans,cnt; int f[N][25],L[N]; inline int read() { int x=0,f=1;char c=getchar(); while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } void init() { for(int j=1;j<=20;j++) for(int i=1;i+(1<<j)-1<=n;i++) f[i][j]=max(f[i][j-1],f[i+(1<<j-1)][j-1]); L[0]=-1; for(int i=1;i<=N;i++) L[i]=L[i/2]+1; } int query(int l,int r) { int k=L[r-l+1]; return max(f[l][k],f[r-(1<<k)+1][k]); } int main() { int x,y; n=read();m=read(); for(int i=1;i<=n;i++) f[i][0]=read(); init(); for(int i=1;i<=m;i++) { x=read();y=read(); printf("%d ",query(x,y)); } return 0; }
左偏树
int merge(int x,int y) { if(x==0) return y; if(y==0) return x;//如果有一个子树是空 if(v[x]<v[y]) swap(x,y);//取较大的根节点权值 r[x]=merge(r[x],y);//将B合并入A的右子树 if(d[l[x]]<d[r[x]]) swap(l[x],r[x]);//维护左偏性质 d[x]=d[r[x]]+1;//更新距离。 return x; } int init(int x) //新建 { v[++tot]=x; l[tot]=r[tot]=d[tot]=0; return tot; } int insert(int x,int y)//新插入一个节点—先建一棵左偏树，再合并。 { merge(x,init(y)); } int pop(int x)//删除堆顶元素。 { return merge(l[x],r[x]); }