【BZOJ1878】【SDOI2009】HH的项链

Author Avatar
q234rty 6月 18, 2016

离线处理+树状数组即可。

将询问按照左端点从小到大排序,之后从左到右扫一遍, t[i] 表示贝壳 i 是否是还没扫过的贝壳中这种颜色的贝壳的第一次出现.

预处理 next[i]​ 表示 a[i]​ 这种颜色的贝壳下一次出现的地方.一开始先把每个颜色第一次出现的贝壳 i​ 的 t[i]​ 加上 1​ .对于每个扫过的贝壳,给 t[next[i]]​ 加上 1​ .

用树状数组维护 t[i] ,询问的答案就是 \sum\limits_{i=l}^r{t[i]} .

于是这题就做完啦.

时间复杂度 O((m+n)\log n) .

Code

  1. #include <cctype>
  2. #include <cstdio>
  3. #include <cstring>
  4. #include <algorithm>
  5. using namespace std;
  6. const int MAXSIZE=30000020;
  7. int bufpos;
  8. char buf[MAXSIZE];
  9. void init(){
  10.     #ifdef LOCAL
  11.         freopen("1878.txt","r",stdin);
  12.     #endif // LOCAL
  13.     buf[fread(buf,1,MAXSIZE,stdin)]='\0';
  14.     bufpos=0;
  15. }
  16. int readint(){
  17.     bool isneg;
  18.     int val=0;
  19.     for(;!isdigit(buf[bufpos]) && buf[bufpos]!='-';bufpos++);
  20.     bufpos+=(isneg=(buf[bufpos]=='-'))?1:0;
  21.     for(;isdigit(buf[bufpos]);bufpos++)
  22.         val=val*10+buf[bufpos]-'0';
  23.     return isneg?-val:val;
  24. }
  25. struct bit{
  26.     int t[50001];
  27.     int n;
  28.     void init(int n){
  29.         this->n=n;
  30.         memset(t,0,sizeof(t));
  31.     }
  32.     inline int lowbit(int x){
  33.         return (x&(-x));
  34.     }
  35.     int sum(int x){
  36.         int ret=0;
  37.         for(int i=x;i>0;i-=lowbit(i))
  38.             ret+=t[i];
  39.         return ret;
  40.     }
  41.     void add(int p,int v){
  42.         for(int i=p;i<=n;i+=lowbit(i))
  43.             t[i]+=v;
  44.         //for(int i=1;i<=n;i++)
  45.         	//printf("%d ",t[i]);
  46.     }
  47. }t;
  48. int nxt[50001];
  49. int now[1000001];
  50. bool app[1000001];
  51. int a[50001];
  52. struct query{
  53.     int l,r,p;
  54.     bool operator <(const query& rhs)const{
  55.         return l<rhs.l;
  56.     }
  57. };
  58. query q[200001];
  59. int ans[200001];
  60. int main(){
  61.     init();
  62.     int n=readint();
  63.     t.init(n);
  64.     for(int i=1;i<=n;i++)
  65.         a[i]=readint();
  66.     int m=readint();
  67.     for(int i=1;i<=m;i++){
  68.         q[i].l=readint(),q[i].r=readint(),q[i].p=i;
  69.     }
  70.     sort(q+1,q+m+1);
  71.     memset(now,-1,sizeof(now));
  72.     for(int i=n;i>=1;i--){
  73.         nxt[i]=now[a[i]];
  74.         now[a[i]]=i;
  75.     }
  76.     for(int i=1;i<=n;i++){
  77.         if (!app[a[i]])
  78.             t.add(i,1),app[a[i]]=true;
  79.     }
  80.     q[0].l=1;
  81.     for(int i=1;i<=m;i++){
  82.         for(int j=q[i-1].l;j<q[i].l;j++)
  83.             if (nxt[j]!=-1)
  84.                 t.add(nxt[j],1);
  86.         ans[q[i].p]=t.sum(q[i].r)-t.sum(q[i].l-1);
  87.     }
  88.     for(int i=1;i<=m;i++)
  89.         printf("%d\n",ans[i]);
  90. }

知识共享许可协议
本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。
本文链接：https://www.q234rty.top/2016/06/18/bzoj1878/

隐藏