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;
}