法一：
BIT + PST (Binary Indexed Tree + Persistent Segment Tree)
BIT + 可持久化線段樹
樹狀數組 + 主席樹
#include <iostream> #include <stdio.h> #include <vector> #include <algorithm> using namespace std; const int MAX_N = 6e4 + 6; const int MAX_P = 4e6 + 6; const int MAX_M = 1e4 + 6; struct Node { static Node mem[MAX_P]; Node *lc,*rc; int sum; Node() { lc=rc=NULL; sum=0; } void pull() { sum = lc->sum + rc->sum; } } Node::mem[MAX_P],*ptr=Node::mem; Node *Build(int L,int R) { Node* node=new(ptr++)Node(); if (L==R) { return node; } int mid=(L+R)>>1; node->lc=Build(L,mid); node->rc=Build(mid+1,R); return node; } Node* getNode(Node* old) { Node* node = new(ptr++)Node(); node->lc=old->lc; node->rc=old->rc; node->sum=old->sum; return node; } void modify(Node* node,Node* old,int L,int R,int pos,int val) { if (L==R) { node->sum += val; return; } int mid=(L+R)>>1; if (pos <= mid) { node->lc=getNode(old->lc); modify(node->lc,old->lc,L,mid,pos,val); } else { node->rc=getNode(old->rc); modify(node->rc,old->rc,mid+1,R,pos,val); } node->pull(); return; } struct Q { int type; int a,b,c; void input() { scanf("%d",&type); if (type==1) scanf("%d %d %d",&a,&b,&c); else scanf("%d %d",&a,&b); } } q[MAX_M]; int a[MAX_N]; Node* root[MAX_N]; Node* bit_root[MAX_N]; int query(Node* L_1tree,Node* Rtree,vector<Node*> bitL_1,vector<Node*> bitR,int L,int R,int k) { if (L==R) { return L; } int sumr = Rtree->lc->sum; int suml = L_1tree->lc->sum; for (auto i:bitL_1) { suml += i->lc->sum; } for (auto i:bitR) { sumr += i->lc->sum; } int mid=(L+R)>>1; if (k <= sumr-suml) { for (Node* &i:bitL_1) { i = i->lc; } for (Node* &i:bitR) { i = i->lc; } return query(L_1tree->lc,Rtree->lc,bitL_1,bitR,L,mid,k); } else { for (Node* &i:bitL_1) { i = i->rc; } for (Node* &i:bitR) { i = i->rc; } return query(L_1tree->rc,Rtree->rc,bitL_1,bitR,mid+1,R,k-sumr+suml); } } int main () { int T; scanf("%d",&T); while (T--) { ptr = Node::mem; int n,m; scanf("%d %d",&n,&m); vector<int> v; for (int i=1;n>=i;i++) { scanf("%d",&a[i]); v.push_back(a[i]); } for (int i=1;m>=i;i++) { q[i].input(); if (q[i].type == 2) v.push_back(q[i].b); } sort(v.begin(),v.end()); v.resize(unique(v.begin(),v.end()) - v.begin()); for (int i=1;n>=i;i++) { a[i]=lower_bound(v.begin(),v.end(),a[i]) - v.begin() +1; } for (int i=1;m>=i;i++) { if (q[i].type == 2) q[i].b = lower_bound(v.begin(),v.end(),q[i].b) - v.begin() + 1; } int nn=v.size(); root[0] = Build(1,nn); for (int i=1;n>=i;i++) { root[i] = getNode(root[i-1]); modify(root[i],root[i-1],1,nn,a[i],1); bit_root[i] = getNode(root[0]); } for (int j=1;m>=j;j++) { if (q[j].type == 3) { puts("7122"); } else if (q[j].type==1) { int L=q[j].a; int R=q[j].b; int k=q[j].c; vector<Node*> bitL_1,bitR; for (int i=R;i>0;i-=(i&(-i))) { bitR.push_back(bit_root[i]); } for (int i=L-1;i>0;i-=(i&(-i))) { bitL_1.push_back(bit_root[i]); } int ret=query(root[L-1],root[R],bitL_1,bitR,1,nn,k); printf("%d\n",v[ret-1]); } else if (q[j].type==2) { int pos=q[j].a; //pos int val=q[j].b; //val int ori=a[pos]; for (int i=pos;n>=i;i+=(i&(-i))) { modify(bit_root[i],bit_root[i],1,nn,ori,-1); } for (int i=pos;n>=i;i+=(i&(-i))) { modify(bit_root[i],bit_root[i],1,nn,val,1); } a[pos] = q[j].b; } } } }
法二：
整體二分
#include <iostream> #include <cstdio> #include <vector> #include <algorithm> #include <cstring> #include <cassert> using namespace std; #define SZ(x) ((int)(x).size()) const int N = 2e5 + 6; int a[N]; struct Event { int time,pos,val,flag; Event(int _time,int _pos,int _val,int _flag):time(_time),pos(_pos),val(_val),flag(_flag){} }; int ans[N]; struct Query { int L,R,k,time,id; Query(int _L,int _R,int _k,int _time,int _id):L(_L),R(_R),k(_k),time(_time),id(_id){} }; struct BIT { int n; int p[N]; void init(int n) { this->n = n; for (int i=0;n>=i;++i) p[i]=0; } void add(int pos,int val) { for (int i=pos;n>=i;i+=i&(-i)) { p[i] += val; } } int qry(int pos) { int ret=0; for (int i=pos;i>=1;i-=i&(-i)) { ret += p[i]; } return ret; } int query(int L,int R) { return qry(R) - qry(L-1); } } bit; void split_event(int mid,vector<Event>& e,vector<Event>& le,vector<Event>& re) { for (Event ee:e) { if (ee.val <= mid) le.push_back(ee); else re.push_back(ee); } vector<Event> ().swap(e); } void totBS(int L,int R,vector<Query> q,vector<Event> e) { if (L==R) { for (Query qq:q) { ans[qq.id] = L; } return; } int mid=(L+R)>>1; vector<Event> le,re; split_event(mid,e,le,re); vector<Query> lq,rq; int eid=-1; for (int i=0;SZ(q)>i;i++) { Query &qq=q[i]; while (eid+1 < SZ(le) && le[eid+1].time <= qq.time) { bit.add(le[eid+1].pos,le[eid+1].flag); eid++; } int ret=bit.query(qq.L,qq.R); if (ret < qq.k) { qq.k -= ret; rq.push_back(qq); } else { lq.push_back(qq); } } while (eid >= 0) { bit.add(le[eid].pos,-le[eid].flag); eid--; } vector<Query> ().swap(q); totBS(L,mid,lq,le); totBS(mid+1,R,rq,re); } int main () { int T; scanf("%d",&T); while (T--) { int n,m; scanf("%d %d",&n,&m); vector<Query> q; vector<Event> e; vector<int> v; for (int i=1;n>=i;++i) { scanf("%d",&a[i]); e.push_back(Event(0,i,a[i],1)); v.push_back(a[i]); } for (int i=1;m>=i;++i) { ans[i] = 0; int type; scanf("%d",&type); if (type == 2) { //change int pos,val; scanf("%d %d",&pos,&val); v.push_back(val); e.push_back(Event(i,pos,a[pos],-1)); e.push_back(Event(i,pos,val,1)); a[pos] = val; } else if (type == 1) { int L,R,k; scanf("%d %d %d",&L,&R,&k); q.push_back(Query(L,R,k,i,i)); } else if (type == 3) { int pos,val; scanf("%d %d",&pos,&val); ans[i] = -2; } } sort(v.begin(),v.end()); v.resize(unique(v.begin(),v.end()) - v.begin()); for (Event &ee:e) { ee.val = lower_bound(v.begin(),v.end(),ee.val) - v.begin() + 1; } bit.init(n); totBS(1,SZ(v),q,e); for (int i=1;m>=i;i++) { if (ans[i] != 0) { if (ans[i] != -2) printf("%d\n",v[ans[i]-1]); else puts("7122"); } } } }
沒有留言:
張貼留言