BZOJ 4408 主席数+找规律

工程师士轩技术 2022年11月9日

0 收藏 904 点赞 4,629 浏览 1532 个字

 #include <cstdio>
 const int Maxn=;
 inline void Get_Int(int &x)
 {
     char ch=getchar(); x=;
     while (ch<'' || ch>'') ch=getchar();
     while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}
 }
 struct Node
 {
     Node * l,* r; int Sum;
     inline void Push_Up() {Sum=l->Sum+r->Sum;}
 };
 Node Memory[Maxn*],* port=Memory,* null,* Root[Maxn];
 int n,m,Mx,a[Maxn],l,r;
 inline int Max(int x,int y) {return x>y?x:y;}
 inline void Init() {null=port++; null->Sum=; null->l=null->r=null;}
 inline Node * NewNode(Node * x)
 {
     Node * Ret=port++;
     if (x==null) {Ret->l=Ret->r=null; Ret->Sum=;} else
         {Ret->l=x->l,Ret->r=x->r,Ret->Sum=x->Sum;}
     return Ret;
 } Node * Insert(Node * Pre,int o,int l,int r,int v)
 {
     Node * Ret=NewNode(Pre);
     if (l==r)
     {
         Ret->Sum+=v;
         return Ret;
     }
     int mid=(l+r)>>;
     if (v<=mid) Ret->l=Insert(Pre->l,o<<,l,mid,v); else Ret->r=Insert(Pre->r,o<<|,mid+,r,v);
     Ret->Push_Up();
 }
 int Sum(Node * Now,int o,int l,int r,int p,int q)
 {
     if (Now==null) return ;
     if (l==p && r<=q) return Now->Sum;
     int mid=(l+r)>>;
     if (q<=mid) return Sum(Now->l,o<<,l,mid,p,q);
     if (p>=mid+) return Sum(Now->r,o<<|,mid+,r,p,q);
     if (p<=mid && q>=mid+) return Sum(Now->l,o<<,l,mid,p,mid)+Sum(Now->r,o<<|,mid+,r,mid+,q);
 }
 inline int Query(int L,int R)
 {
     int Ret=;
     while (true)
     {
         int t=Sum(Root[R],,,Mx,,Ret)-Sum(Root[L],,,Mx,,Ret);
         if (t<Ret) return Ret; else Ret=t+;
     }
     return Ret;
 }
 int main()
 {
     // freopen("data.in","r",stdin);
     // freopen("data.out","w",stdout);
     Init();
     Get_Int(n);
     for (int i=;i<=n;i++) Get_Int(a[i]),Mx=Max(Mx,a[i]);
     Root[]=NewNode(null);
     for (int i=;i<=n;i++) Root[i]=Insert(Root[i-],,,Mx,a[i]);
     Get_Int(m);
     for (int i=;i<=m;i++)
     {
         Get_Int(l),Get_Int(r);
         printf("%d\n",Query(l-,r));
     }
     return ;
 }