-
个人简介
#include<bits/stdc++.h> using namespace std; const int maxn=100000,maxt=maxn<<1,maxl=18,maxb=9,maxc=maxt/maxb; struct node{ int val; int dep,dfn,end; node *son[2]; }T[maxn]; int n,t,b,c,Log2[maxc+1]; int Pos[(1<<(maxb-1))+5],Dif[maxc+1]; node *root,*A[maxt],*Min[maxl][maxc]; void build(){ static node *S[maxn+1]; int top=0; for(int i=0;i<n;i++){ node *p=&T[i]; while(top&&S[top]->val<p->val)p->son[0]=S[top]; if(top)p->son[1]=S[top]; S[++top]=p; } root=S[1]; } void DFS(node *p){ A[p->dfn=t++]=p; for(int i=0;i<2;i++) if(p->son[i]){ p->son[i]->dep=p->dep+1; DFS(p->son[i]); A[t++]=p; } p->end=t-1; } node *min(node *x,node *y){ return x->dep<y->dep?x:y; } void ST_init(){ b=(int)(ceil(log2(t)/2)); c=t/b; Log2[1]=0; for(int i=2;i<=c;i++)Log2[i]=Log2[i>>1]+1; for(int i=0;i<c;i++){ Min[0][i]=A[i*b]; for(int j=1;j<b;j++)Min[0][i]=min(Min[0][i],A[i*b+j]); } for(int i=1,l=2;l<=c;i++,l<<=1) for(int j=0;j+l<=c;j++)Min[i][j]=min(Min[i-1][j],Min[i-1][j+(l>>1)]); } void small_init(){ for(int i=0;i<c;i++) for(int j=1;j<b&&i*b+j<t;j++) if(A[i*b+j]->dep<A[i*b+j-1]->dep)Dif[i]|=1<<(j-1); for(int S=0;S<(1<<(b-1));S++){ int mx=0,v=0; for(int i=1;i<b;i++){ v+=(S>>(i-1)&1)?-1:1; if(v<mx){ mx=v; Pos[S]=i; } } } } node *ST_query(int l,int r){ int g=Log2[r-l+1]; return min(Min[g][l],Min[g][r-(1<<g)+1]); } node *small_query(int l,int r){ int p=l/b; int S=(Dif[p]>>(l-p*b))&((1<<(r-1))-1); return A[l+Pos[S]]; } node *query(int l,int r){ if(l>r)return query(r,l); int pl=l/b,pr=r/b; if(pl==pr)return small_query(l,r); else{ node *s=min(small_query(l,pl*b+b-1),small_query(pr*b,r)); if(pl+1<=pr-1)s=min(s,ST_query(pl+1,pr-1)); return s; } } int main(){ int m; cin>>n>>m; for(int i=0;i<n;i++)cin>>T[i].val; build(); DFS(root); ST_init(); small_init(); while(m--){ int l,r; cin>>l>>r; cout<<query(T[l].dfn,T[r].dfn)->val<<endl; } return 0; }
#include<bits/stdc++.h> #define N 100010 using namespace std; int n,a[N]; struct tree{ int l,r; int sum; int add; }t[N<<2]; void pushup(int p){ t[p].sum=t[p<<1].sum+t[p<<1|1].sum; } void pushdown(int p){ auto &root=t[p],&left=t[p<<1],&right=t[p<<1|1]; if(root.add){ left.add+=root.add; left.sum+=(left.r-left.l+1)*root.add; right.add+=root.add; right.sum+=(right.r-right.l+1)*root.add; root.add=0; } } void build(int p,int l,int r){ t[p].l=l,t[p].r=r; if(l==r){ t[p].sum=a[l]; return; } int mid=l+r>>1; build(p<<1,l,mid); build(p<<1|1,mid+1,r); pushup(p); } void modify(int p,int l,int r,int d){ if(l<=t[p].l&&t[p].r<=r){ t[p].sum+=(t[p].r-t[p].l+1)*d; t[p].add+=d; return; } pushdown(p); int mid=t[p].l+t[p].r>>1; if(l<=mid)modify(p<<1,l,r,d); if(r>mid)modify(p<<1|1,l,r,d); pushup(p); } int query(int p,int l,int r){ if(l<=t[p].l&&t[p].r<<r)return t[p].sum; pushdown(p); int mid=t[p].l+t[p].r>>1; int sum=0; if(l<=mid)sum+=query(p<<1,l,r); if(r>mid)sum+=query(p<<1|1,l,r); return sum; } int main(){ cin>>n; for(int i=1;i<=n;i++)cin>>a[i]; int x,v,l,r; build(1,1,n); modify(1,x,v,1); query(1,l,r); return 0; }
n=int(input()) a=list(map(int,input().split())) st=[0]*n top=-1 cur=1 flag=True for i in range(n): while a[i]>=cur: top+=1 st[top]=cur cur+=1 if st[top]==a[i]: top-=1 else: flag=False print("NO") break if flag and i==n-1 and top==-1: print("YES")
#include<bits/stdc++.h> using namespace std; const int maxn=105; unsigned ack(unsigned m,unsigned n){ if(m==0)return n+1; if(n==0)return ack(m-1,1); return ack(m-1,ack(m,n-1)); } int main(){ unsigned m,n; cin>>m>>n; cout<<ack(m,n)<<endl; return 0; }
http://10.209.85.202/noi/2023chusai/08_2020CSP-S/2020级提高级试题.pdf
-
最近活动
This person is lazy and didn't join any contests or homework.