SPOJ3267 D-query 离线+树状数组 在线主席树

分析：这个题，离线的话就是水题，如果强制在线，其实和离线一个思路，然后硬上主席树就行了

离线的代码

  

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int N = 1e6+5;
const int maxn= 3e4+5;
const int INF=0x3f3f3f3f;
typedef unsigned long long ULL;
typedef long long LL;
int n,a[maxn],pre[maxn],mp[N],res[maxn*7],q;
struct Que{
  int l,r,id;
  bool operator<(const Que &rhs)const{
     return r<rhs.r;
  }
}o[maxn*7];

int c[maxn];
void add(int x,int t){
  for(int i=x;i<=n;i+=i&(-i))
    c[i]+=t;
}
int get(int x){
  int ans=0;
  for(int i=x;i>0;i-=i&(-i))
    ans+=c[i];
  return ans;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
      scanf("%d",&a[i]);
      pre[i]=mp[a[i]];
      mp[a[i]]=i; 
    }
    scanf("%d",&q);
    for(int i=1;i<=q;++i)
     scanf("%d%d",&o[i].l,&o[i].r),o[i].id=i;
    sort(o+1,o+1+q);
    int cnt=1;
    for(int i=1;i<=q;++i){
      for(;cnt<=o[i].r;++cnt){
       if(pre[cnt])add(pre[cnt],-1);
       add(cnt,1); 
      }
      res[o[i].id]=get(o[i].r)-get(o[i].l-1);
    }
    for(int i=1;i<=q;++i)printf("%d
",res[i]); 
    return 0;
}

在线，其实感觉比离线好写呢。。

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int N = 1e6+5;
const int maxn= 3e4+5;
const int INF=0x3f3f3f3f;
typedef unsigned long long ULL;
typedef long long LL;
int n,mp[N],q;
struct Node{
  int l,r,v;
}o[30*maxn];
int root[maxn],sz;
void update(int &rt,int l,int r,int pos,int t){
  o[++sz]=o[rt],rt=sz;
  o[rt].v+=t;
  if(l==r)return;
  int m=(l+r)>>1;
  if(pos<=m)update(o[rt].l,l,m,pos,t);
  else update(o[rt].r,m+1,r,pos,t);
}
int query(int rt,int l,int r,int x,int y){
   if(x<=l&&r<=y)
    return o[rt].v;
   int m=(l+r)>>1;
   int ans=0;
   if(x<=m)ans+=query(o[rt].l,l,m,x,y);
   if(y>m)ans+=query(o[rt].r,m+1,r,x,y);
   return ans;
}
int main(){
    scanf("%d",&n); 
    root[0]=sz=0;
    for(int i=1;i<=n;++i){
      int x;
      scanf("%d",&x);
      if(mp[x]){
        int tmp;
        update(tmp=root[i-1],1,n,mp[x],-1);
        update(root[i]=tmp,1,n,i,1);
      }
      else update(root[i]=root[i-1],1,n,i,1);
      mp[x]=i;
    }
    scanf("%d",&q);
    for(int i=1;i<=q;++i){
        int l,r;
        scanf("%d%d",&l,&r);
        printf("%d
",query(root[r],1,n,l,r));
    }
    return 0;
}