题意:
刷墙, 以开始 有 n个节点,每个节点有一种颜色 ,m 次询问
m次 输入 a,l,r,z 如果 a=1 将 l到 r 刷为 z 颜色,如果 a=2 询问 l 到 r 有 多少个 和 z 相同的 节点
官方题解是: 分段哈希,自己一开始想写 一下 ,单写着写着 就 觉得很麻烦 ,各中判断条件。。。。。
后来改为 线段树 优化了下 ,就是加了 个 mi mx 判断 查询的颜色 是否在这里面。。。。。
1 #include<cstdio> 2 #include<cstring> 3 #include<cmath> 4 #include<iostream> 5 #include<algorithm> 6 #include< set> 7 #include<map> 8 #include<queue> 9 #include<vector> 10 #include< string> 11 #define Min(a,b) a<b?a:b 12 #define Max(a,b) a>b?a:b 13 #define CL(a,num) memset(a,num,sizeof(a)); 14 #define maxn 100010 15 #define eps 1e-6 16 #define inf 9999999 17 #define ll __int64 18 using namespace std; 19 struct node 20 { 21 int l; 22 int r; 23 int c; 24 int mi; 25 int mx; 26 }p[maxn* 4]; 27 int a[maxn] ; 28 void build( int x, int l, int r) 29 { 30 if(l == r) 31 { 32 p[x].l = l; 33 p[x].r = r; 34 p[x].c= a[l]; 35 p[x].mi = a[l]; 36 p[x].mx = a[l]; 37 return ; 38 } 39 int mid = (l+r)>> 1; 40 p[x].l = l; 41 p[x].r = r; 42 build(x* 2,l,mid); 43 build(x* 2+ 1,mid+ 1,r); 44 if(p[x* 2].c == p[x* 2+ 1].c &&p[x* 2].c != - 1)p[x].c = p[x* 2].c; 45 else p[x].c = - 1; 46 47 p[x].mi = min(p[x* 2].mi,p[x* 2+ 1].mi); 48 p[x].mx = max(p[x* 2].mx,p[x* 2+ 1].mx); 49 50 51 52 } 53 void change( int x, int l, int r, int z) 54 { 55 if(z == p[x].c) return; 56 if(l == p[x].l&&r == p[x].r) 57 { 58 p[x].c = z ; 59 p[x].mi = z; 60 p[x].mx = z; 61 62 return ; 63 64 } 65 int mid = (p[x].l+p[x].r)>> 1; 66 if(p[x].c != - 1) 67 { 68 p[x* 2].c = p[x].c; 69 p[x* 2+ 1].c = p[x].c; 70 p[x* 2].mi =p[x* 2+ 1].mi = p[x].mi;//这两个忘了 下分了 错了 一次。。。。。。。。 71 p[x* 2].mx=p[x* 2+ 1].mx = p[x].mx; 72 p[x].c = - 1; 73 } 74 75 if(r<=mid) change(x* 2,l,r,z); 76 else 77 { 78 if(l>mid)change(x* 2+ 1,l,r,z); 79 else 80 { 81 change(x* 2,l,mid,z); 82 change(x* 2+ 1,mid+ 1,r,z); 83 } 84 } 85 p[x].mi = min(p[x* 2].mi,p[x* 2+ 1].mi); 86 p[x].mx = max(p[x* 2].mx,p[x* 2+ 1].mx); 87 } 88 int get( int x, int l, int r, int z) 89 { 90 if(p[x].c!=- 1 &&p[x].c!=z) return 0; 91 if(z<p[x].mi ||z>p[x].mx) return 0; 92 93 if(p[x].l <= l&&p[x].r >= r&&p[x].c == z) 94 { 95 return r - l + 1; 96 } 97 int mid = (p[x].l + p[x].r)>> 1; 98 99 if(r<=mid) return get(x* 2,l,r,z); 100 else 101 { 102 if(l>mid) return get(x* 2+ 1,l,r,z); 103 else 104 { 105 int t1 = get(x* 2,l,mid,z); 106 int t2 = get(x* 2+ 1,mid+ 1,r,z); 107 return t1+t2; 108 } 109 } 110 111 112 113 } 114 115 int main() 116 { 117 int n,m,d,l,r,z,i; 118 // freopen("data.in","r",stdin); 119 while(scanf( " %d%d ",&n,&m)!=EOF) 120 { 121 for(i = 0; i < n;i++) 122 { 123 scanf( " %d ",&a[i]); 124 } 125 build( 1, 0,n - 1); 126 while(m--) 127 { 128 scanf( " %d%d%d%d ",&d,&l,&r,&z); 129 if(d == 1) 130 { 131 change( 1,l,r,z); 132 } 133 else 134 { 135 int ans = get( 1,l,r,z); 136 printf( " %d\n ",ans); 137 } 138 } 139 } 140 }