题意：
一个区间支持三种操作，区间加，区间开根号和区间求和。
题解：
线段树的做法。对于区间开根号操作，如果要开根号的区间最大值和最小值相等的话相当于区间减操作。当最大值和最小值相差1时，如果最大值是平方数那么也相当于区间减操作，否则就是区间覆盖。
#include <iostream> #include <cstdio> #include <cmath> #include <algorithm> #define lson (id<<1) #define rson ((id<<1)|1) #define mid ((l+r)>>1) using namespace std; typedef long long ll; const int N = 1e5+10; int n, m; int t, l, r; ll x; ll lazy[N*5], maxx[N*5], minn[N*5], sum[N*5]; void push_up(int id) { maxx[id] = max(maxx[lson], maxx[rson]); minn[id] = min(minn[lson], minn[rson]); sum[id] = sum[lson]+sum[rson]; } void build(int id, int l, int r) { lazy[id] = 0; if(l==r) { scanf("%lld", &sum[id]); maxx[id] = minn[id] = sum[id]; return ; } build(lson, l, mid); build(rson, mid+1, r); push_up(id); return ; } void push_down(int id, int l, int r) { if(lazy[id]) { lazy[lson] += lazy[id]; lazy[rson] += lazy[id]; sum[lson] += 1ll*(mid-l+1)*lazy[id]; sum[rson] += 1ll*(r-mid)*lazy[id]; maxx[lson] += lazy[id]; maxx[rson] += lazy[id]; minn[lson] += lazy[id]; minn[rson] += lazy[id]; lazy[id] = 0; } } void ins(int id, int l, int r, int ql, int qr, ll x) { if(ql<=l&&r<=qr) { sum[id] += 1ll*(r-l+1)*x; lazy[id] += x; maxx[id] += x; minn[id] += x; return ; } push_down(id, l, r); if(ql<=mid) ins(lson, l, mid, ql, qr, x); if(qr>mid) ins(rson, mid+1, r, ql, qr, x); push_up(id); } void update(int id, int l, int r, int ql, int qr) { if(ql<=l&&r<=qr&&maxx[id]-minn[id]<=1) { ll k = (ll)sqrt(maxx[id]); if(maxx[id]-minn[id]==0||k*k==maxx[id]) { ins(id, l, r, l, r, k-maxx[id]); return ; } } push_down(id, l, r); if(ql<=mid) update(lson, l, mid, ql, qr); if(qr>mid) update(rson, mid+1, r, ql, qr); push_up(id); } ll query(int id, int l, int r, int ql, int qr) { if(ql<=l&&r<=qr) return sum[id]; push_down(id, l, r); ll res = 0; if(ql<=mid) res += query(lson, l, mid, ql, qr); if(qr>mid) res += query(rson, mid+1, r, ql, qr); push_up(id); return res; } int main() { scanf("%d%d", &n, &m); build(1, 1, n); while(m--) { scanf("%d%d%d", &t, &l, &r); if(t==1) { scanf("%lld", &x); ins(1, 1, n, l, r, x); } if(t==2) update(1, 1, n, l, r); if(t==3) printf("%lld\n", query(1, 1, n, l, r)); } }