首先，分块的复杂度是，但是现在要求根号，对于INT_MAX，取五次根号就可以到1了，所以我们只用判到1即可。
#include <iostream> #include <cstdio> #include <cmath> #include <string> #include <cstring> #include <algorithm> #include <limits> #include <vector> #include <stack> #include <queue> #include <set> #include <map> #include <unordered_map> #include <unordered_set> #define lowbit(x) ( x&(-x) ) #define pi 3.141592653589793 #define e 2.718281828459045 #define INF 0x3f3f3f3f #define eps 1e-6 #define HalF (l + r)>>1 #define lsn rt<<1 #define rsn rt<<1|1 #define Lson lsn, l, mid #define Rson rsn, mid+1, r #define QL Lson, ql, qr #define QR Rson, ql, qr #define myself rt, l, r using namespace std; typedef unsigned long long ull; typedef unsigned int uit; typedef long long ll; const int maxN = 5e4 + 7; int N, Q, len, s, a[maxN]; struct K { int l, r, sum; K(int a=0, int b=0, int c=0):l(a), r(b), sum(c) {} inline int len() { return r - l + 1; } }t[240]; inline void update(int ql, int qr) { int st = (ql - 1) / len + 1, ed = (qr - 1) / len + 1; if(st == ed) { if(t[st].sum == t[st].len()) return; for(int i=ql; i<=qr; i++) { if(a[i] == 1) continue; t[st].sum -= a[i]; a[i] = sqrt(a[i]); t[st].sum += a[i]; } return; } if(t[st].len() < t[st].sum) { for(int i=ql; i<=t[st].r; i++) { if(a[i] == 1) continue; t[st].sum -= a[i]; a[i] = sqrt(a[i]); t[st].sum += a[i]; } } if(t[ed].len() < t[ed].sum) { for(int i=t[ed].l; i<=qr; i++) { if(a[i] == 1) continue; t[ed].sum -= a[i]; a[i] = sqrt(a[i]); t[ed].sum += a[i]; } } for(int i = st + 1; i <= ed - 1; i++) { if(t[i].sum == t[i].len()) continue; for(int j=t[i].l; j <= t[i].r; j++) { if(a[j] == 1) continue; t[i].sum -= a[j]; a[j] = sqrt(a[j]); t[i].sum += a[j]; } } } inline int query(int ql, int qr) { int ans = 0; int st = (ql - 1) / len + 1, ed = (qr - 1) / len + 1; if(st == ed) { if(t[st].sum == t[st].len()) return qr - ql + 1; for(int i=ql; i <= qr; i++) { ans += a[i]; } return ans; } if(t[st].sum == t[st].len()) ans += t[st].r - ql + 1; else { for(int i=ql; i<=t[st].r; i++) ans += a[i]; } if(t[ed].sum == t[ed].len()) ans += qr - t[ed].l + 1; else { for(int i=t[ed].l; i<=qr; i++) ans += a[i]; } for(int i = st + 1; i <= ed - 1; i++) ans += t[i].sum; return ans; } int main() { scanf("%d", &N); Q = N; for(int i=1; i<=N; i++) scanf("%d", &a[i]); len = sqrt(N); s = N / len + (N % len == 0 ? 0 : 1); for(int i=1; i<=s; i++) { t[i].l = (i - 1) * len + 1; t[i].r = i * len; } t[s].r = N; for(int i=1; i<=s; i++) for(int j=t[i].l; j<=t[i].r; j++) t[i].sum += a[j]; int op, l, r, c; while(Q--) { scanf("%d%d%d%d", &op, &l, &r, &c); if(op) { printf("%d\n", query(l, r)); } else { update(l, r); } } return 0; }
