可持久化线段树

　　这次是询问一段区间内权值 在给定范围内的点的数量，同样是可持久化线段树简单操作……

1 //Vijos 1923 2 #include
      
         3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
             8 #define rep(i,n) for(int i=0;i
            
             =n;--i)11 using namespace std;12 13 int getint(){14 int v=0,sign=1; char ch=getchar();15 while(ch<'0'||ch>'9') { if (ch=='-') sign=-1; ch=getchar();}16 while(ch>='0'&&ch<='9') {v=v*10+ch-'0'; ch=getchar();}17 return v*=sign;18 }19 #define debug20 /*******************tamplate********************/21 const int N=100086;22 23 int root[N],n,m,cnt;24 struct Tree{25 int l,r,cnt;26 }t[N*30];27 28 struct node{29 int val,num,rank;30 bool operator < (const node&now)const{31 return val
             
              >1)40 void update(int &o,int l,int r,int pos){41 t[++cnt]=t[o]; o=cnt; ++t[o].cnt;42 if(l==r)return;43 if(pos<=mid) update(t[o].l,l,mid,pos);44 else update(t[o].r,mid+1,r,pos);45 }46 47 int _sum,ql,qr;48 void query(int i,int j,int l,int r){49 if (ql<=l && qr>=r) _sum+=t[j].cnt-t[i].cnt;50 else{51 if (ql<=mid) query(t[i].l,t[j].l,l,mid);52 if (qr> mid) query(t[i].r,t[j].r,mid+1,r);53 }54 }55 #undef mid56 int main(){57 n=getint(); m=getint();58 F(i,1,n) {a[i].val=getint(); a[i].num=i;}59 sort(a+1,a+n+1);60 int rank=0,tot=0;61 F(i,1,n) if(a[i].val!=a[i-1].val){62 a[i].rank=++rank;63 b[++tot]=a[i].val;64 }65 else a[i].rank=rank;66 67 sort(a+1,a+n+1,cmp);68 69 F(i,1,n){70 root[i]=root[i-1];71 update(root[i],1,n,a[i].rank);72 }73 int l,r,k,w;74 F(i,1,m){75 l=getint(); r=getint(); k=getint(); w=getint();76 ql=lower_bound(b+1,b+tot+1,k)-b;77 qr=upper_bound(b+1,b+tot+1,w)-b-1;//!!!78 _sum=0;79 query(root[l-1],root[r],1,n);80 printf("%d\n",_sum);81 }82 return 0;83 }