Original link: https://www.shuizilong.com/house/archives/luogu-3765/
#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.