NPCA Judge 97:永続segtree
問題文
http://judge.npca.jp/problems/view/97
参考にさせていただきました
http://sigma425.hatenablog.com/entry/2014/12/30/164148
i回目のループで、x回目のループ終了時点での配列aの[l,r)の区間に含まれる数の個数を答えるので永続segtreeが必要。
#include<iostream> #include<vector> #include<algorithm> #include<cassert> using namespace std; typedef long long ll; struct node_t{ int num; node_t *lch,*rch; node_t(node_t *l,node_t *r,int n):num(n),lch(l),rch(r){} node_t(node_t *l,node_t *r):lch(l),rch(r){ num=(l?l->num:0)+(r?r->num:0); } node_t(){} }; node_t tree[5000000]; node_t *root[200005]; //root[number_of_query] struct PersistentSegmentTree{ private: int numOfNode,now,cur; node_t *nil; node_t *new_node(node_t *lch,node_t *rch,int num){ return &(tree[cur++]=node_t(lch,rch,num)); } node_t *new_node(node_t *lch,node_t *rch){ return &(tree[cur++]=node_t(lch,rch)); } node_t *update(int id, int l,int r, node_t *t){ if(r-l<=1)return new_node(nil,nil,t->num+1); int m=(l+r)/2; if(id<m)return new_node(update(id,l,m,t->lch),t->rch); else return new_node(t->lch,update(id,m,r,t->rch)); } int query(int a,int b,int l,int r,node_t *t){ if(t==nil)return 0; if(b<=l || r<=a)return 0; if(a<=l && r<=b)return t->num; int m=(l+r)/2; return query(a,b,l,m,t->lch)+query(a,b,m,r,t->rch); } public: PersistentSegmentTree(int n):numOfNode(n),now(0),cur(0){ root[0]=nil=new_node(0,0,0); nil->lch=nil->rch=nil; } void update(int id){ root[now+1]=update(id,0,numOfNode,root[now]); now++; } int query(int a,int b,int x){ return query(a,b,0,numOfNode,root[x]); } }; int main(void){ int n; cin >> n; vector<int>l(n),r(n); for(int i=0;i<n;i++)cin >> l[i]; for(int i=0;i<n;i++)cin >> r[i]; PersistentSegmentTree t(n); int x=0; for(int i=0;i<n;i++){ t.update(x); ll cnt=t.query(l[i],r[i],x+1); x=(cnt*l[i]+r[i])%(i+2); //cout << x << " " << cnt << endl; } cout << x << endl; return 0; }