分块（查询区间内和k相同的数在把区间内的数改为k

 1 #include<bits/stdc++.h>
 2 
 3 using namespace std;
 4 typedef long long ll;
 5 const int maxn = 1e5 + 10;
 6 const int inf = 0x3f3f3f3f;
 7 int dir[10][10] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
 8 int pos[maxn], l[maxn], r[maxn], v[maxn], lz[maxn]; // lz数组判定整个块是否都为同一个数，不是-1就是区间都为lz的值。
 9 int a, b, c, t, n;
10 
11 inline int read()
12 {
13     char ch = getchar(); int k = 0, f = 1;
14     while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
15     while(ch >= '0' && ch <= '9') {k = (k << 1) + (k << 3) + ch - '0'; ch = getchar();}
16     return k * f;
17 }
18 
19 inline void reset(int x)
20 {
21     if(lz[x] == -1) return ;
22     for(int i = l[x]; i <= r[x]; ++i) v[i] = lz[x]; //lz非-1的话说明此块里都是lz的值
23     lz[x] = -1; 
24 }
25 inline int findy(int a,int b,int c)
26 {
27     int pa = pos[a], pb = pos[b], ans = 0;
28     if(pa == pb)
29     {
30         reset(pa);
31         for(int i = a; i <= b; ++i)
32         {
33             if(v[i] == c) ans++; v[i] = c;
34         }
35         lz[pa] = -1; // 进行了修改就不能保证lz块里一定是同一个数了
36     }
37     else
38     {
39         reset(pa);
40         for(int i = a; i <= r[pa]; ++i) {if(v[i] == c) ans++; v[i] = c;}
41         reset(pb);
42         for(int i = l[pb]; i <= b; ++i) {if(v[i] == c) ans++; v[i] = c;}
43         for(int i = pa + 1; i <= pb - 1; ++i)
44         {
45             int k = 0;
46             if(lz[i] != -1)
47             {
48                 if(lz[i] == c) ans += (r[i] - l[i] + 1);
49                 else lz[i] = c;
50             }
51             else
52             {
53                 for(int j = l[i]; j <= r[i]; ++j)
54                 {
55                     if(v[j] == c) ans++; v[j] = c;
56                 }
57                 lz[i] = c;
58             }
59         }
60     }
61     return ans;
62 }
63 int main()
64 {
65     n = read();
66     for(int i = 1; i <= n; ++i)
67     {
68         v[i] = read();
69     }
70     t = sqrt(n);
71     for(int i = 1; i <= t; ++i)
72     {
73         l[i] = (i-1) * t + 1;
74         r[i] = i * t;
75     }
76     if(r[t] != n) t++, l[t] = r[t - 1] + 1, r[t] = n;
77     for(int i = 1; i <= t; ++i)
78     {
79         for(int j = l[i]; j <= r[i]; ++j)
80         {
81             pos[j] = i;
82         }
83     }
84     memset(lz, -1, sizeof(lz));
85     for(int i = 1; i <= n; ++i)
86     {
87         a = read(); b = read(); c = read();
88         cout<<findy(a, b, c)<<endl;
89     }
90     return 0;
91 }
分块 （查询区间内和k相同的数在把区间内的数改为k

分块（查询区间内和k相同的数在把区间内的数改为k
