hdu 4391 块状链表或线段树+剪枝

方法1：块状链表

PS：块状链表太强大了，也可以实现和线段树一样的lazy操作来提高效率。每个块维护自己块的信息，这个题中可以考虑每个块维护一个map来记录每个颜色在区间中出现了多少次。

  1 #include <iostream>
  2 #include <cstring>
  3 #include <cstdio>
  4 #include <cmath>
  5 #include <map>
  6 using namespace std;
  7 
  8 const int M = 400;
  9 int b[M][M];
 10 int n, m, ps;
 11 int lazy[M];
 12 map<int, int> mp[M];
 13 
 14 void down( int i )
 15 {
 16     if ( lazy[i] == -1 ) return ;
 17     for ( int j = 0; j < ps && i * ps + j < n; j++ )
 18     {
 19         b[i][j] = lazy[i];
 20     }
 21     lazy[i] = -1;
 22 }
 23 
 24 int query( int l, int r, int v )
 25 {
 26     int cur = l / ps, ncur = r / ps;
 27     l = l % ps, r = r % ps;
 28     int res = 0;
 29     for ( int i = cur + 1; i < ncur; i++ )
 30     {
 31         if ( mp[i].count(v) )
 32         {
 33             res += mp[i][v];
 34         }
 35     }
 36     if ( cur != ncur )
 37     {
 38         down(cur);
 39         for ( int j = l; j < ps; j++ )
 40         {
 41             if ( b[cur][j] == v ) res++;
 42         }
 43         down(ncur);
 44         for ( int j = 0; j <= r; j++ )
 45         {
 46             if ( b[ncur][j] == v ) res++;
 47         }
 48     }
 49     else
 50     {
 51         down(cur);
 52         for ( int j = l; j <= r; j++ )
 53         {
 54             if ( b[cur][j] == v ) res++;
 55         }
 56     }
 57     return res;
 58 }
 59 
 60 void update( int l, int r, int v )
 61 {
 62     int cur = l / ps, ncur = r / ps;
 63     l = l % ps, r = r % ps;
 64     for ( int i = cur + 1; i < ncur; i++ )
 65     {
 66         mp[i].clear();
 67         mp[i][v] = ps;
 68         lazy[i] = v;
 69     }
 70     if ( cur != ncur )
 71     {
 72         down(cur);
 73         for ( int j = l; j < ps; j++ )
 74         {
 75             mp[cur][b[cur][j]]--;
 76             b[cur][j] = v;
 77         }
 78         mp[cur][v] += ps - l;
 79         down(ncur);
 80         for ( int j = 0; j <= r; j++ )
 81         {
 82             mp[ncur][b[ncur][j]]--;
 83             b[ncur][j] = v;
 84         }
 85         mp[ncur][v] += r + 1;
 86     }
 87     else
 88     {
 89         down(cur);
 90         for ( int j = l; j <= r; j++ )
 91         {
 92             mp[cur][b[cur][j]]--;
 93             b[cur][j] = v;
 94         }
 95         mp[cur][v] += r - l + 1;
 96     }
 97 }
 98 
 99 int main ()
100 {
101     ps = 350;
102     while ( scanf("%d%d", &n, &m) != EOF )
103     {
104         memset( lazy, -1, sizeof(lazy) );
105         for ( int i = 0; i < M; i++ ) mp[i].clear();
106         for ( int i = 0; i < n; i++ )
107         {
108             int tmp;
109             scanf("%d", &tmp);
110             b[i / ps][i % ps] = tmp;
111             mp[i / ps][tmp]++;
112         }
113         int a, l, r, z;
114         while ( m-- )
115         {
116             scanf("%d%d%d%d", &a, &l, &r, &z);
117             if ( a == 1 )
118             {
119                 update( l, r, z );
120             }
121             else
122             {
123                 printf("%d
", query( l, r, z ));
124             }
125         }
126     }
127     return 0;
128 }

方法2：线段树+剪枝

普通的线段树是会TLE的，所以在结点上多维护两个值：maxn和minn，如果要查询的颜色大于最大或小于最小则返回0，剪枝后比方法1快了许多，此外还有几个很容易想到的剪枝，具体见代码。

  1 #include <iostream>
  2 #include <cstring>
  3 #include <cstdio>
  4 using namespace std;
  5 
  6 const int N = 100001;
  7 int color[N];
  8 
  9 struct Node
 10 {
 11     int l, r, lazy, maxn, minn;
 12 } node[N << 2];
 13 
 14 void pushup( int i )
 15 {
 16     int lc = i << 1, rc = lc | 1;
 17     node[i].maxn = max( node[lc].maxn, node[rc].maxn );
 18     node[i].minn = min( node[lc].minn, node[rc].minn );
 19 }
 20 
 21 void build( int i, int l, int r )
 22 {
 23     node[i].l = l, node[i].r = r, node[i].lazy = -1;
 24     if ( l == r )
 25     {
 26         node[i].maxn = node[i].minn = node[i].lazy = color[l];
 27         return ;
 28     }
 29     int mid = ( l + r ) >> 1;
 30     build( i << 1, l, mid );
 31     build( i << 1 | 1, mid + 1, r );
 32     pushup(i);
 33 }
 34 
 35 void pushdown( int i )
 36 {
 37     if ( node[i].lazy != -1 )
 38     {
 39         int lc = i << 1, rc = lc | 1;
 40         node[lc].lazy = node[rc].lazy = node[i].lazy;
 41         node[lc].maxn = node[rc].maxn = node[i].lazy;
 42         node[lc].minn = node[rc].minn = node[i].lazy;
 43         node[i].lazy = -1;
 44     }
 45 }
 46 
 47 void update( int i, int l, int r, int val )
 48 {
 49     if ( node[i].lazy == val ) return ;
 50     if ( node[i].l == l && node[i].r == r )
 51     {
 52         node[i].maxn = node[i].minn = node[i].lazy = val;
 53         return ;
 54     }
 55     pushdown(i);
 56     int mid = ( node[i].l + node[i].r ) >> 1;
 57     if ( r <= mid )
 58     {
 59         update( i << 1, l, r, val );
 60     }
 61     else if ( l > mid )
 62     {
 63         update( i << 1 | 1, l, r, val );
 64     }
 65     else
 66     {
 67         update( i << 1, l, mid, val );
 68         update( i << 1 | 1, mid + 1, r, val );
 69     }
 70     pushup(i);
 71 }
 72 
 73 int query( int i, int l, int r, int val )
 74 {
 75     if ( node[i].maxn < val || node[i].minn > val ) return 0;
 76     if ( node[i].lazy != -1 )
 77     {
 78         if ( node[i].lazy == val ) return r - l + 1;
 79         else return 0;
 80     }
 81     int mid = ( node[i].l + node[i].r ) >> 1;
 82     if ( r <= mid )
 83     {
 84         return query( i << 1, l, r, val );
 85     }
 86     else if ( l > mid )
 87     {
 88         return query( i << 1 | 1, l, r, val );
 89     }
 90     else
 91     {
 92         return query( i << 1, l, mid, val ) + query( i << 1 | 1, mid + 1, r, val );
 93     }
 94 }
 95 
 96 int main ()
 97 {
 98     int n, m;
 99     while ( scanf("%d%d", &n, &m) != EOF )
100     {
101         for ( int i = 1; i <= n; i++ )
102         {
103             scanf("%d", color + i);
104         }
105         build( 1, 1, n );
106         int op, a, b, c;
107         while ( m-- )
108         {
109             scanf("%d%d%d%d", &op, &a, &b, &c);
110             a++, b++;
111             if ( op == 1 )
112             {
113                 update( 1, a, b, c );
114             }
115             else
116             {
117                 printf("%d
", query( 1, a, b, c ));
118             }
119         }
120     }
121     return 0;
122 }