题意： 对一个长度为10W 的数组进行如下三种操作：
1，区间[l,r]的数都加上x;
2，区间内的没个数都开根号（向下取整）；
3，求区间[l,r]每个元素的和。
官方题解：
但是官方标程也被卡T了。据说hack数据是：10万个2，3，2，3，2，3.......,10万个操作 加6，开根。但是题的确不错。
在本题中我并没有按照官方题解的方法。我们可以想下，发现区间的最大值，最小值的差值会随着开方的次数越来越小。再加上又是区间内的数都加上一个值。
那么我们可以只需要考虑区间内极差小于2的区间即可。刚好我们需要维护区间最大值，最小值。
那么当区间的极差为0时，表示区间内的数都相同，直接开方，该区间的值都覆盖为sqrt(maxx); 区间的最大值，最小值，和，最大值的数量，最小值的数量自然就出来了
当区间的极差为1时，很显然最大值，最小值，及其它们的数量就表示出了区间的所有数。最大值最小值，自然也出来了。
a[i]<10W 那么对整个区间内的每个数开方的次数就很少了。 当开了一定次方之后整个区间内的数的差值就很接近了。
代码如下：
#include<iostream> #include<algorithm> #include<stdio.h> #include<vector> #include<string.h> #include<map> #include<queue> #include<stack> #include<string> #include<stdlib.h> #include<time.h> #include<set> #include<math.h> using namespace std; typedef long long ll; const int nn = 600100; const int inf = (1 << 31); const ll mod = 998244353; const ll g = 3;//mod的原根，当且仅当 g^(MOD-1) = 1 % MOD #define pb push_back #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 struct FastIO { static const int S = 1310720; int wpos; char wbuf[S]; FastIO() : wpos(0) {} inline int xchar() { static char buf[S]; static int len = 0, pos = 0; if (pos == len) pos = 0, len = fread(buf, 1, S, stdin); if (pos == len) return -1; return buf[pos++]; } inline int xuint() { int c = xchar(), x = 0; while (c <= 32) c = xchar(); for (; '0' <= c && c <= '9'; c = xchar()) x = x * 10 + c - '0'; return x; } inline int xint() { int s = 1, c = xchar(), x = 0; while (c <= 32) c = xchar(); if (c == '-') s = -1, c = xchar(); for (; '0' <= c && c <= '9'; c = xchar()) x = x * 10 + c - '0'; return x * s; } inline ll xll() { ll s = 1, c = xchar(), x = 0; while (c <= 32) c = xchar(); if (c == '-') s = -1, c = xchar(); for (; '0' <= c && c <= '9'; c = xchar()) x = x * 10 + c - '0'; return x * s; } inline void xstring(char *s) { int c = xchar(); while (c <= 32) c = xchar(); for (; c > 32; c = xchar()) *s++ = c; *s = 0; } inline void wchar(int x) { if (wpos == S) fwrite(wbuf, 1, S, stdout), wpos = 0; wbuf[wpos++] = x; } inline void wint(int x) { if (x < 0) wchar('-'), x = -x; char s[24]; int n = 0; while (x || !n) s[n++] = '0' + x % 10, x /= 10; while (n--) wchar(s[n]); } inline void wstring(const char *s) { while (*s) wchar(*s++); } ~FastIO() { if (wpos) fwrite(wbuf, 1, wpos, stdout), wpos = 0; } } io; struct node { ll minn, maxx,sum;//区间最小值，最大值，区间和 ll maxnum, minnum;//区间最大值，最小值的数量 ll all;//区间覆盖为all,0表示没覆盖 ll lazy;//区间内的数都加上lazy； }; int n, m; node t[nn << 2]; void pushup(int rt) { t[rt].sum = t[rt << 1].sum + t[rt << 1 | 1].sum; t[rt].maxx = max(t[rt << 1].maxx, t[rt << 1 | 1].maxx); t[rt].minn = min(t[rt << 1].minn, t[rt << 1 | 1].minn); t[rt].maxnum = t[rt].minnum = 0; if (t[rt].maxx == t[rt << 1].maxx) t[rt].maxnum += t[rt << 1].maxnum; if (t[rt].maxx == t[rt << 1 | 1].maxx) t[rt].maxnum += t[rt << 1 | 1].maxnum; if (t[rt].minn == t[rt << 1].minn) t[rt].minnum += t[rt << 1].minnum; if (t[rt].minn == t[rt << 1 | 1].minn) t[rt].minnum += t[rt << 1 | 1].minnum; } void pushdown(int rt,int l,int r) { int mid = (l + r) >> 1; if (t[rt].all)//区间覆盖 { t[rt << 1].all = t[rt << 1 | 1].all = t[rt].all; t[rt << 1].sum = (ll)(mid - l + 1)*t[rt].all; t[rt << 1 | 1].sum = (ll)(r - mid)*t[rt].all; t[rt << 1].minn = t[rt << 1].maxx = t[rt << 1 | 1].maxx = t[rt << 1 | 1].minn = t[rt].all; t[rt << 1].minnum = t[rt << 1].maxnum = (ll)(mid - l + 1); t[rt << 1 | 1].maxnum = t[rt << 1 | 1].minnum = (ll)(r - mid); t[rt << 1].lazy = t[rt << 1 | 1].lazy = 0; t[rt].all = 0; } if (t[rt].lazy)//区间+lazy { t[rt << 1].lazy += t[rt].lazy; t[rt << 1 | 1].lazy += t[rt].lazy; t[rt << 1].sum += (ll)(mid - l + 1)*t[rt].lazy; t[rt << 1 | 1].sum += (ll)(r - mid)*t[rt].lazy; t[rt << 1].minn += t[rt].lazy; t[rt << 1 | 1].minn += t[rt].lazy; t[rt << 1].maxx += t[rt].lazy; t[rt << 1 | 1].maxx += t[rt].lazy; t[rt].lazy = 0; } } void build(int l, int r, int rt) { t[rt].all = t[rt].lazy = 0; if (l == r) { t[rt].sum = t[rt].maxx = t[rt].minn = io.xll(); t[rt].maxnum = t[rt].minnum = 1; return; } int mid = (l + r) >> 1; build(lson); build(rson); pushup(rt); } void add(int l, int r, int rt, int L, int R, ll x) { if (L <= l && r <= R) { t[rt].sum += (ll)(r - l + 1)*x; t[rt].maxx += x; t[rt].minn += x; t[rt].lazy += x; return; } pushdown(rt, l, r); int mid = (l + r) >> 1; if (L <= mid) add(lson, L, R, x); if (R > mid) add(rson, L, R, x); pushup(rt); } void t_sqrt(int l, int r, int rt, int L, int R) { if (L <= l && r <= R && (t[rt].maxx - t[rt].minn) <= 1) { if (t[rt].maxx == 1) return; ll x = t[rt].maxx; if (t[rt].maxx == t[rt].minn) { t[rt].minn = t[rt].maxx = floor(sqrt(x)); t[rt].lazy += t[rt].maxx-x; t[rt].sum = (ll)(r - l + 1)*t[rt].maxx; } else { t[rt].maxx = floor(sqrt(t[rt].maxx)); t[rt].minn = floor(sqrt(t[rt].minn)); if (t[rt].maxx == t[rt].minn) { t[rt].maxnum = t[rt].minnum = (ll)(r - l + 1); t[rt].lazy = 0; t[rt].all = t[rt].maxx; t[rt].sum = t[rt].maxx*t[rt].maxnum; } else { t[rt].lazy += t[rt].maxx - x; t[rt].sum = t[rt].maxx*t[rt].maxnum + t[rt].minn*t[rt].minnum; } } return; } int mid = (l + r) >> 1; pushdown(rt, l, r); if (L <= mid) t_sqrt(lson, L, R); if (R > mid) t_sqrt(rson, L, R); pushup(rt); } ll query(int l, int r, int rt, int L, int R) { if (L <= l && r <= R) { return t[rt].sum; } int mid = (l + r) >> 1; pushdown(rt, l, r); ll ans = 0; if (L <= mid) ans += query(lson, L, R); if (R > mid) ans += query(rson, L, R); return ans; } int main() { int t = io.xint(); while (t--) { n = io.xll(); m = io.xll(); build(1,n,1); while (m--) { int op = io.xint(); int l = io.xint(); int r = io.xint(); if (op == 1) { ll x = io.xll(); add(1, n, 1, l, r, x); } else if (op == 2) { t_sqrt(1, n, 1, l, r); } else { printf("%lld\n", query(1, n, 1, l, r)); } } } return 0; }加不加输入外挂都是能过的。但是必须要交G++ 不然就算加了输入外挂一样TLE
