【BZOJ3236】【AHOI2013】作业

Author Avatar
q234rty 2月 17, 2017

莫队算法即可。

注意到修改有 O((m+n)\sqrt n) 次，而询问只有 O(m) 次，考虑用一个询问 O(\sqrt n) ，修改 O(1) 的权值分块来维护当前书的集合，总时间复杂度 O((m+n)\sqrt n) 。

Code

  1. #include <cctype>
  2. #include <cstdio>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <cmath>
  6. using namespace std;
  7. const int MAXSIZE=40000020;
  8. int bufpos;
  9. char buf[MAXSIZE];
  10. void init(){
  11.     buf[fread(buf,1,MAXSIZE,stdin)]='\0';
  12.     bufpos=0;
  13. }
  14. int readint(){
  15.     int val=0;
  16.     for(;!isdigit(buf[bufpos]);bufpos++);
  17.     for(;isdigit(buf[bufpos]);bufpos++)
  18.         val=val*10+buf[bufpos]-'0';
  19.     return val;
  20. }
  21. struct block{
  22.     int n,sz,num;
  23.     int sum[321],o[321];
  24.     int cnt[100001];
  25.     int w[100001];
  26.     int st[321];
  27.     void init(int n){
  28.         sz=sqrt(n)+0.5;
  29.         num=(n-1)/sz+1;
  30.         st[1]=1;
  31.         for(int i=1;i<=n;i++)
  32.             w[i]=(i-1)/sz+1;
  33.         for(int i=2;i<=num;i++)
  34.             st[i]=st[i-1]+sz;
  35.         st[num+1]=n+1;
  36.     }
  37.     void update(int x,int sgn){
  38.         if (!cnt[x])
  39.             o[w[x]]++;
  40.         cnt[x]+=sgn;
  41.         sum[w[x]]+=sgn;
  42.         if (!cnt[x])
  43.             o[w[x]]--;
  44.     }
  45.     pair<int,int> query(int a,int b){
  46.         int res1=0,res2=0;
  47.         if (w[a]==w[b]){
  48.             for(int i=a;i<=b;i++)
  49.                 res1+=cnt[i],res2+=!!cnt[i];
  50.             return make_pair(res1,res2);
  51.         }
  52.         for(int i=w[a]+1;i<w[b];i++)
  53.             res1+=sum[i],res2+=o[i];
  54.         for(int i=a;i<st[w[a]+1];i++)
  55.             res1+=cnt[i],res2+=!!cnt[i];
  56.         for(int i=st[w[b]];i<=b;i++)
  57.             res1+=cnt[i],res2+=!!cnt[i];
  58.         return make_pair(res1,res2);
  59.     }
  60. }t;
  61. int sz;
  62. struct query{
  63.     int p,l,r,a,b;
  64.     bool operator <(const query& rhs)const{
  65.         return l/sz!=rhs.l/sz?l/sz<rhs.l/sz:r<rhs.r;
  66.     }
  67. }q[1000001];
  68. int a[100001];
  69. pair<int,int> ans[1000001];
  70. int main(){
  71.     init();
  72.     int n=readint(),m=readint();
  73.     sz=sqrt(n)+0.5;
  74.     for(int i=1;i<=n;i++)
  75.         a[i]=readint();
  76.     for(int i=1;i<=m;i++)
  77.         q[i].p=i,q[i].l=readint(),q[i].r=readint(),q[i].a=readint(),q[i].b=readint();
  78.     sort(q+1,q+m+1);
  79.     int l=1,r=0;
  80.     t.init(n);
  81.     for(int i=1;i<=m;i++){
  82.         while(l<q[i].l)
  83.             t.update(a[l++],-1);
  84.         while(r<q[i].r)
  85.             t.update(a[++r],1);
  86.         while(l>q[i].l)
  87.             t.update(a[--l],1);
  88.         while(r>q[i].r)
  89.             t.update(a[r--],-1);
  90.         ans[q[i].p]=t.query(q[i].a,q[i].b);
  91.     }
  92.     for(int i=1;i<=m;i++)
  93.         printf("%d %d\n",ans[i].first,ans[i].second);
  94. }

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

隐藏