Luogu P3765 Presidential Election

Original link: https://www.shuizilong.com/house/archives/luogu-3765/

blank.jpg

   #include <lastweapon/io>   #include <bits/stdc++.h>   #include <ext/pb_ds/tree_policy.hpp>   #include <ext/pb_ds/assoc_container.hpp>   using namespace __gnu_pbds;   using namespace lastweapon;      #define ls id<<1   #define rs id<<1|1      const int N = int(5e5) + 9;   int k,aa[N];      struct xd_node   {       int l,r;       int cnt,num;//Maintain a serial number of cnt and mode like the problem of finding mode}treee[4*N];   struct xd_treee   {       void change(int id)       {           if(treee[ls].num==treee[rs].num) treee[id].num=treee[ls].num,treee[id].cnt=treee[ls].cnt+treee[rs]. cnt;           else           {               if(treee[ls].cnt>=treee[rs].cnt) treee[id].cnt=treee[ls].cnt-treee[rs].cnt,treee[id].num=treee[ls]. num;               else treee[id].cnt=treee[rs].cnt-treee[ls].cnt,treee[id].num=treee[rs].num;           }       }       void build(int id, int l, int r)       {           treee[id].l=l; treee[id].r=r;           if(l==r)           {               treee[id].cnt=1;               treee[id].num=aa[l];               return;           }           int mid=(l+r)>>1;           build(ls,l,mid); build(rs,mid+1,r);           change(id);       }       void updata(int id, int pos, int w)       {           if(treee[id].l==pos&&treee[id].r==pos)           {               treee[id].num=w;               treee[id].cnt=1;               return;           }           int mid=(treee[id].l+treee[id].r)>>1;           if(mid>=pos) updata(ls,pos,w);           else updata(rs,pos,w);           change(id);       }       xd_node search(int id,int l,int r)       {           if(treee[id].l==l&&treee[id].r==r) return treee[id];           int mid=(treee[id].l+treee[id].r)>>1;           if(mid>=r) return search(ls,l,r);           else if(mid<l) return search(rs,l,r);           else           {               xd_node a=search(ls,l,mid),b=search(rs,mid+1,r),c;               if(a.num==b.num) c.num=a.num,c.cnt=a.cnt+b.cnt;               else               {                   if(a.cnt>=b.cnt) c.cnt=a.cnt-b.cnt,c.num=a.num;                   else c.cnt=b.cnt-a.cnt,c.num=b.num;               }               return c;           }       }   }a;         tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> T[N];      int main()   {   #ifndef ONLINE_JUDGE       freopen("in.txt", "r", stdin);       //freopen("out.txt", "w", stdout);   #endif          int n,m;       scanf("%d%d",&n,&m);       for(int i=1;i<=n;i++) {               scanf("%d",&aa[i]);               T[aa[i]].insert(i);       }          a.build(1,1,n);       for(int i=1;i<=m;i++) {           int l,r,s,q; RD(l,r,s);           int x=a.search(1,l,r).num;           int sum=T[x].order_of_key(r+1)-T[x].order_of_key(l);           if(sum>(r-l+1)/2) s=x;           Rush {               RD(x); a.updata(1,x,s);               if (aa[x] != s) {                   T[aa[x]].erase(x); aa[x]=s;                   T[aa[x]].insert(x);               }           }           OT(s);       }       int x=a.search(1,1,n).num;       OT(SZ(T[x]) > n/2 ? x :-1);   }      

This article is reproduced from: https://www.shuizilong.com/house/archives/luogu-3765/
This site is for inclusion only, and the copyright belongs to the original author.

Leave a Comment