分块（区间根号，区间查询

题目大意就是给你一个区间在区间的各个数都开个根号，然后在让你区间求和

主要思路就是如果需更新区间全是0或者全是1就可以不用管。这题我用了set，头尾指针指的值相等且为0或者1就满足条件。

  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 color[maxn], l[maxn], r[maxn], pos[maxn], v[maxn], sum[maxn], lz[maxn], t;
  9 set<int> s[1010];
 10 
 11 inline int read() //快读
 12 {
 13     char ch = getchar(); ll 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 p)
 20 {
 21     s[p].clear();
 22     s[p].insert(v + l[p], v + r[p] + 1);  //自动从小到大排序
 23     set<int>::iterator it, itt;
 24     it = s[p].begin(); itt = s[p].end(); itt--;   //左闭右开，否则s.end()返回的应该是s.size()
 25     if(sqrt(*it) == 1 && sqrt(*itt) == 1) color[p] = 1;
 26     if(sqrt(*it) == 0 && sqrt(*itt) == 0) color[p] = 1;  
 27 }
 28 
 29 inline void inser(int a, int b)
 30 {
 31     int pa = pos[a], pb = pos[b];
 32     if(pa == pb)
 33     {
 34         for(int i = a; i <= b; ++i)
 35         {
 36             sum[pa] -= v[i];
 37             v[i] = sqrt(v[i]);
 38             sum[pa] += v[i];
 39         }
 40         reset(pa);
 41     }
 42     else
 43     {
 44         for(int i = a; i <= r[pa]; ++i)
 45         {
 46             sum[pa] -= v[i];
 47             v[i] = sqrt(v[i]);
 48             sum[pa] += v[i];
 49         }
 50         reset(pa);
 51 
 52         for(int i = l[pb]; i <= b; ++i)
 53         {
 54             sum[pb] -= v[i];
 55             v[i] = sqrt(v[i]);
 56             sum[pb] += v[i];
 57         }
 58         reset(pb);
 59 
 60         for(int i = pa + 1; i <= pb - 1; ++i)
 61         {
 62             if(color[i]==0)  //如果不是全为1或者0的区间就要进行更新
 63             {
 64                 for(int j = l[i]; j <= r[i]; ++j)
 65                 {
 66                     sum[i] -= v[j];
 67                     v[j] = sqrt(v[j]);
 68                     sum[i] += v[j];
 69                 }
 70                 reset(i);
 71             }
 72         }
 73 
 74     }
 75 }
 76 
 77 inline int findy(int a, int b)
 78 {
 79     int pa = pos[a], pb = pos[b], ans = 0;
 80     if(pa == pb)
 81     {
 82         for(int i = a; i <= b; ++i) ans += v[i];
 83     }
 84     else
 85     {
 86         for(int i = a; i <= r[pa]; ++i) ans += v[i];
 87         for(int i = l[pb]; i <= b; ++i) ans += v[i];
 88         for(int i = pa + 1; i <= pb - 1; ++i)
 89         {
 90             ans += sum[i];
 91         }
 92     }
 93     return ans;
 94 }
 95 
 96 int main()
 97 {
 98     int n, opt, a, b, c;
 99     n = read();
100     for(int i = 1; i <= n; ++i) v[i] = read();
101     t = sqrt(n);
102     for(int i = 1; i <= t; ++i)
103     {
104         l[i] = (i-1) * t + 1;
105         r[i] = i * t;
106     }
107 
108     if(r[t] != n) t++, l[t] = r[t - 1] + 1, r[t] = n;
109 
110     for(int i = 1; i <= t; ++i)
111     {
112         for(int j = l[i]; j <= r[i]; ++j)
113         {
114             pos[j] = i; s[i].insert(j); sum[i] += v[j];  //初始化
115         }
116     }
117 
118     for(int i = 1; i <= n; ++i)
119     {
120         opt = read(); a = read(); b = read(); c = read();
121         if(opt == 0) inser(a, b);
122         else cout<<findy(a, b)<<endl;
123     }
124 
125     return 0;
126 }

另外需要提下的是RTE和TLE不一定是正常情况，还有可能是用了快读又关了同步流，即getchar()和scanf printf类似，用cin cout再用这些都不能关闭同步流。（直接用scanf printf就没这么多事

虽然没发生在我身上。。但是一直检查对的代码也是很痛苦的

也告诉我们学东西要学透彻别老想一知半解