[HUST1407 山东省队选拔赛2008 郁闷的小J]【离线算法】【二分】【树状数组】★★

【题目连接】http://acm.hust.edu.cn/thx/problem.php?id=1407 （中文题目）

【算法分析】

这是一个好题。

首先有一个通用解法，平衡树+线段树，不过几乎肯定超时。（在线算法）

然后我YY到一个很经典的东西。P[j]-P[i-1]就得到i..j的信息。

于是对于一个询问，Q i j w。其实我们只要知道w在前j-1个位置有多少个，和w在前i个位置有多少个。就能通过一个减法得到答案。

然后我们把我们需要的信息抽出来。只维护他们。

每个信息的结构如下。{int Num,pos,key;}。其中Num表示询问的w。pos表示前pos个位置。key表示前pos个位置，Num出现几次？

然后我们观察假如change了一个数a[i]=p -> a[i]=w，该变的是哪些信息？

第一类，删除旧信息。对于所有Num=p，且pos>=i的信息，我们将他的key–

第二类，增加新信息。对于所有Num=w，且pos>=i的信息，我们将他的key++

好了。这里面我们需要的东西就显而易见了。

把信息按Num为第一关键字，pos为第二关键字排序，然后可以很容易用树状数组 or 线段树维护起来。

当然，我们当前位置+1。后面Num>w的是没有必要减回来的。因为我们最后是通过减法运算嘛。会互相抵消的。

【其它】

Orz。再删除了一次冗余的东西以后。排到了第一。

1 48386(2) edward_mj 4560 KB 1432 MS C++ 2382 B 2010-07-29 15:53:57 2 47267 lshmouse 6144 KB 1568 MS C++ 2727 B 2010-07-26 21:30:03 3 48114 foreverlin 5480 KB 1804 MS C++ 4771 B 2010-07-29 01:32:38 4 48102 WhatIsGenius 8548 KB 3128 MS C++ 1965 B 2010-07-28 23:09:53

【CODE】

#include #include #include #include #include using namespace std;
const int N=105555;
int n,m,tot;
int a[N];
struct Qu_t{int op,x,y,z;}Query[N];
struct List_t{int Num,pos;}L[N*2];
int Tr[N*2];

void init(){
     tot=0;
     scanf("%d%d",&n,&m);
     int i;
     for (i=1;i<=n;i++)
       scanf("%d",&a[i]);
     char tmp[10];
     for (i=1;i<=m;i++){
         scanf("%s",tmp);
         if (tmp[0]==’Q’){
           Query[i].op=0;
           scanf("%d%d%d",&Query[i].x,&Query[i].y,&Query[i].z);
           L[++tot].Num=Query[i].z; L[tot].pos=Query[i].y;
           L[++tot].Num=Query[i].z; L[tot].pos=Query[i].x-1;
         }
         else{
           Query[i].op=1;
           scanf("%d%d",&Query[i].x,&Query[i].y);
         }
     }
}

inline bool cmp(List_t A,List_t B){
     if (A.Num!=B.Num) return A.Num     return A.pos}

inline void Add(int k,int x){
     for (;k<=tot;k+=k&-k) Tr[k]+=x;
}

inline int Get_Sum(int k){
    int res=0;
    for (;k>0;k-=k&-k) res+=Tr[k];
    return res;
}

inline int Find(int key,int pos){
    int l=1,r=tot,mid;
    while (l      mid=(l+r)>>1;
      if (L[mid].Num                                                          else r=mid;
    }
    return l;
}

void pre_do(){
     sort(L+1,L+tot+1,cmp);
     int tmp=tot,i,x;
     tot=0;
     for (i=1;i<=tmp;i++){
         tot+=(i==1 || L[i].Num!=L[i-1].Num || L[i].pos!=L[i-1].pos);
         L[tot]=L[i];
     }
     for (i=1;i<=tot;i++) Tr[i]=0;
     for (i=1;i<=n;i++){
         x=Find(a[i],i);
         if (L[x].Num==a[i] && L[x].pos>=i) Add(x,1);
     }
}

void solve(){
     int i,j,x,y;
     for (i=1;i<=m;i++)
       if (Query[i].op==0){
         x=Get_Sum( Find ( Query[i].z,Query[i].y ) );
         y=Get_Sum( Find ( Query[i].z,Query[i].x-1 ) );
         printf("%dn",x-y);
       }
       else{
         x=Find(a[Query[i].x],Query[i].x);
         if (L[x].Num==a[Query[i].x] && L[x].pos>=Query[i].x) Add(x,-1);
        
         a[Query[i].x]=Query[i].y;
        
         x=Find(a[Query[i].x],Query[i].x);
         if (L[x].Num==a[Query[i].x] && L[x].pos>=Query[i].x) Add(x,1);
       }
}

int main(){
    init();
    pre_do();
    solve();
}