sol：不难吧，首先假设所有的狮子会一口气吃到底，（只剩一只），
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int N=100005,inf=2e9+7; int n,a[N],rt,re[N],pp,pre[N]; struct segtree{int l,r,mi,ma,miid,maid;inline int mid(){return (l+r)>>1;}}Tree[N<<2]; #define c1 x<<1 #define c2 x<<1|1 inline void Ami(int x,int y){Tree[x].mi=Tree[y].mi;Tree[x].miid=Tree[y].miid;} inline void Ama(int x,int y){Tree[x].ma=Tree[y].ma;Tree[x].maid=Tree[y].maid;} inline void Up(int x){if(Tree[c1].mi!=Tree[c2].mi){if(Tree[c1].mi<Tree[c2].mi)Ami(x,c1); else Ami(x,c2);}else Ami(x,c1);if(Tree[c1].ma!=Tree[c2].ma){if(Tree[c1].ma>Tree[c2].ma)Ama(x,c1); else Ama(x,c2);}else Ama(x,c2);} inline void build(int l,int r,int x){Tree[x].l=l;Tree[x].r=r;if(l==r){Tree[x].mi=Tree[x].ma=a[l];Tree[x].maid=Tree[x].miid=l;return;}int mid=(l+r)>>1;build(l,mid,c1);build(mid+1,r,c2); Up(x);} inline void ins(int po,int x,int v){if(Tree[x].l==Tree[x].r){Tree[x].mi=Tree[x].ma=v;return;}int mid=Tree[x].mid();if(po<=mid)ins(po,c1,v);else ins(po,c2,v); Up(x);} inline void del(int po,int x){if(Tree[x].l==Tree[x].r){Tree[x].mi=inf;Tree[x].ma=-1;return;}int mid=Tree[x].mid();if(po<=mid)del(po,c1);else del(po,c2); Up(x);} int main() { int i,p1,p2; scanf("%d",&n); for(i=1;i<=n;i++)scanf("%d",&a[i]); build(1,n,1); pp=n-1; for(i=1;i<n;i++) { p1=Tree[1].miid; p2=Tree[1].maid; pre[p2]=i; a[p2]-=a[p1]; del(p1,1); ins(p2,1,a[p2]); re[i]=p1; } for(i=n-1;i>=1;i=min(--i,pp)) { if(pre[re[i]])pp=pre[re[i]]-1; }printf("%d ",pp); sort(re+1,re+pp+1); for(i=1;i<pp;i++)printf("%d ",re[i]);printf("%d ",re[pp]); }
sol：线段树裸题，多打打胆子练大点，这种题应该很快就能过
维护8个标记，左边的高度，左边相同的点的个数，左边这段连续的是否合法（即左段最右边是否大于右边那个数），右边和左边维护一样的三个标记，再维护答案，lazy，这段数字这否全部相同
#include <cstdio> #include <algorithm> using namespace std; const int N=200005; int n,Q,h,cnt=0,has[N<<1]; struct node{int l,r,v;}as[N]; struct segtree{int l,r,s,lh,ln,lc,rh,rn,rc,ok,laz;inline int mid(){return (l+r)>>1;}inline int len(){return (r-l+1);}}Tree[N<<2]; #define c1 x<<1 #define c2 x<<1|1 inline void Up(int x) { Tree[x].s=Tree[c1].s+Tree[c2].s; Tree[x].lh=Tree[c1].lh; Tree[x].rh=Tree[c2].rh; Tree[x].lc=Tree[c1].lc;Tree[x].rc=Tree[c2].rc; if(Tree[c1].ok){if(Tree[c1].rh>Tree[c2].lh)Tree[x].lc=1;else if(Tree[c1].rh==Tree[c2].lh)Tree[x].lc=Tree[c2].lc;} if(Tree[c2].ok){if(Tree[c2].lh>Tree[c1].rh)Tree[x].rc=1;else if(Tree[c2].lh==Tree[c1].rh)Tree[x].rc=Tree[c1].rc;} if(Tree[c1].ok){if(Tree[c1].rh==Tree[c2].lh)Tree[x].ln=Tree[c1].len()+Tree[c2].ln;else Tree[x].ln=Tree[c1].len();}else Tree[x].ln=Tree[c1].ln; if(Tree[c2].ok){if(Tree[c2].lh==Tree[c1].rh)Tree[x].rn=Tree[c2].len()+Tree[c1].rn;else Tree[x].rn=Tree[c2].len();}else Tree[x].rn=Tree[c2].rn; if(Tree[c1].ok&&Tree[c2].ok&&Tree[c1].rh==Tree[c2].lh)Tree[x].ok=1;else Tree[x].ok=0; if(Tree[c1].rh!=Tree[c2].lh) { if(Tree[c1].rh>Tree[c2].lh) { if(Tree[c1].rc) Tree[x].s+=has[Tree[c1].r]-has[Tree[c1].r-Tree[c1].rn+1]+1; }else if(Tree[c2].lc) Tree[x].s+=has[Tree[c2].l+Tree[c2].ln-1]-has[Tree[c2].l]+1; }else if(Tree[c1].rc&&Tree[c2].lc)Tree[x].s+=has[Tree[c2].l+Tree[c2].ln-1]-has[Tree[c1].r-Tree[c1].rn+1]+1; } inline void Ad(int x,int v){Tree[x].laz+=v; Tree[x].lh+=v; Tree[x].rh+=v;} inline void Down(int x){if(Tree[x].laz){Ad(c1,Tree[x].laz);Ad(c2,Tree[x].laz);Tree[x].laz=0;}} inline void build(int l,int r,int x) { Tree[x].l=l; Tree[x].r=r; if(l==r) { Tree[x].lh=Tree[x].rh=h; Tree[x].ln=Tree[x].rn=Tree[x].ok=1; return; }int mid=(l+r)>>1; build(l,mid,c1); build(mid+1,r,c2); Up(x); } inline void ins(int l,int r,int x,int v) { if(Tree[x].l==l&&Tree[x].r==r){Ad(x,v);return;} Down(x); int mid=Tree[x].mid(); if(r<=mid)ins(l,r,c1,v);else if(l>mid)ins(l,r,c2,v);else ins(l,mid,c1,v),ins(mid+1,r,c2,v); Up(x); } int main() { int i,x,y,v; scanf("%d%d%d",&n,&Q,&h); has[++cnt]=1; has[++cnt]=n; for(i=1;i<=Q;i++) { scanf("%d%d%d",&x,&y,&v); has[++cnt]=x; has[++cnt]=y; as[i]=(node){x,y,v}; if(x>1)has[++cnt]=x-1; if(y<n)has[++cnt]=y+1; }sort(has+1,has+cnt+1); cnt=unique(has+1,has+cnt+1)-has-1; for(i=1;i<=Q;i++) { as[i].l=lower_bound(has+1,has+cnt+1,as[i].l)-has; as[i].r=lower_bound(has+1,has+cnt+1,as[i].r)-has; }build(1,cnt,1); for(i=1;i<=Q;i++) { ins(as[i].l,as[i].r,1,as[i].v); printf("%d ",Tree[1].s); } }
#include <cmath> #include <cstdio> #include <cctype> #include <cstring> using namespace std; inline int read(){int s=0,f=0; char ch; while(!isdigit(ch)){f|=(ch=='-');ch=getchar();} while(isdigit(ch)){s=s*10+ch-'0';ch=getchar();} return f?-s:s;} #define r(x) x=read() const int N=1200005; int n,md[10],fa[N],sz[N],tong[N]; inline void solve(int x) { int i,j,s=0; for(i=2;i<=n;i++) { fa[i]=(fa[i]+x)%(i-1); if(fa[i]<0)fa[i]+=i;else fa[i]++; }memset(sz,0,sizeof sz); memset(tong,0,sizeof tong); for(i=n;i>=1;i--){sz[i]++;sz[fa[i]]+=sz[i];} for(i=1;i<=n;i++)tong[sz[i]]++; for(i=1;i<=n;i++) if(n%i==0) { s=0; for(j=i;j<=n;j+=i)s+=tong[j]; if(s>=n/i)printf("%d ",i); } } int main() { int i,x; r(n); for(i=1;i<=9;i++)r(md[i]); md[0]=-1; for(i=2;i<=n;i++){r(x);fa[i]=x;} for(i=0;i<=9;i++) { printf("Case #%d: ",i+1); solve(md[i]); }return 0; }