bzoj 3809 莫队

收获：

　　1、分块时顺便记录每个位置所属的块，然后一次排序就OK了。

　　2、要权衡在“区间移动”与“查询结果”之间的时间，莫队算法一般区间移动频率远大于查询结果，所以我们选择的辅助数据结构时就要注意了，我最开始写的是值域线段树，自己生成的极限数据要1m8s，改成树状数组后要24s，还是过不了，hzwer只要13s，细看hzwer的代码，发现Ta用的是分块，O(1)修改O(n^0.5)查询，改成分块后的确快多了。

　　3、块的大小理论最优值是O(n*m^-0.5)，最开始设成这个交上去35卡过，改成hzwer的n/2后29s，所以做题时要自己试一下。

  1 /**************************************************************
  2     Problem: 3809
  3     User: idy002
  4     Language: C++
  5     Result: Accepted
  6     Time:29336 ms
  7     Memory:26988 kb
  8 ****************************************************************/
  9  
 10 #include <cstdio>
 11 #include <cctype>
 12 #include <cstring>
 13 #include <cmath>
 14 #include <algorithm>
 15 #define maxn 100010
 16 #define maxm 1000010
 17 #define lowbit(i) ((i)&(-(i)))
 18 using namespace std;
 19  
 20  
 21 int n, m;
 22 int lx[maxn], rx[maxn], mccno[maxn], stot;
 23 int w[maxn];
 24 int ans[maxm];
 25 int cnt[maxn], siz[maxn], cmc[maxn];
 26  
 27  
 28 struct Qu {
 29     int l, r, a, b, id;
 30     bool operator<( const Qu & c ) const {
 31         return mccno[l]<mccno[c.l] || ( mccno[l]==mccno[c.l] && r<c.r );
 32     }
 33 };
 34 Qu qu[maxm];
 35  
 36 void add( int pos ) {
 37     siz[pos]++;
 38     if( siz[pos]==1 ) cmc[mccno[pos]]++;
 39 }
 40 void del( int pos ) {
 41     siz[pos]--;
 42     if( siz[pos]==0 ) cmc[mccno[pos]]--;
 43 }
 44 int query( int l, int r ) {
 45     int lm = mccno[l], rm = mccno[r];
 46     int rt = 0;
 47     if( lm==rm ) {
 48         for( int j=l; j<=r; j++ )
 49             if( siz[j] ) rt++;
 50         return rt;
 51     }
 52     for( int b=lm+1; b<rm; b++ )
 53         rt += cmc[b];
 54     for( int j=l; j<=rx[lm]; j++ )
 55         if( siz[j] ) rt++;
 56     for( int j=lx[rm]; j<=r; j++ )
 57         if( siz[j] ) rt++;
 58     return rt;
 59 }
 60 void partition() {
 61     int len = (int)ceil(sqrt(n/2)+1);
 62     stot = n/len;
 63     rx[0] = 0;
 64     for( int i=1; i<=stot; i++ ) {
 65         lx[i] = rx[i-1]+1;
 66         rx[i] = rx[i-1]+len;
 67     }
 68     if( rx[stot]!=n ) {
 69         stot++;
 70         lx[stot] = rx[stot-1]+1;
 71         rx[stot] = n;
 72     }
 73     for( int i=1; i<=stot; i++ ) 
 74         for( int j=lx[i]; j<=rx[i]; j++ )
 75             mccno[j] = i;
 76 }
 77 void work() {
 78     sort( qu+1, qu+1+m);
 79  
 80     int lf = qu[1].l;
 81     int rg = qu[1].r;
 82     for( int j=lf; j<=rg; j++ )
 83         add(w[j]);
 84     ans[qu[1].id] = query( qu[1].a, qu[1].b );
 85     for( int q=2; q<=m; q++ ) {
 86         while( qu[q].l<lf ) add(w[--lf]);
 87         while( qu[q].l>lf ) del(w[lf++]);
 88         while( qu[q].r>rg ) add(w[++rg]);
 89         while( qu[q].r<rg ) del(w[rg--]);
 90         ans[qu[q].id] = query( qu[q].a, qu[q].b );
 91     }
 92 }
 93 int main() {
 94     scanf( "%d%d", &n, &m );
 95     for( int i=1; i<=n; i++ )
 96         scanf( "%d", w+i );
 97     for( int i=1; i<=m; i++ ) {
 98         scanf( "%d%d%d%d", &qu[i].l, &qu[i].r, &qu[i].a, &qu[i].b );
 99         qu[i].id = i;
100     }
101     partition();
102     work();
103     for( int i=1; i<=m; i++ ) 
104         printf( "%d
", ans[i] );
105 }

View Code