bzoj3211
输出格式：每次x=1时，每行一个整数，表示这次旅行的开心度
解析：已经写了好几次这种题了，这次来水水博客 QAQ~ 不难发现对于数列中的每一个数，被进行操作后改变的次数是很少的。 于是可以记录下每一段区间是否已经全部变成了1（变成1后再进行操作数仍不变），对于全是1的区间不用再进行操作。 这样我们可以对每一个不全是1的区间暴力修改，最后统计一下和即可。
代码如下：
#include<cstdio> #include<algorithm> #include<cmath> #define ll long long #define lc o << 1 #define rc o << 1 | 1 using namespace std; const int maxn = 1e5 + 5; int n, a[maxn], q, bj[maxn * 4]; ll sum[maxn * 4]; int read(void) { char c; while (c = getchar(), c < '0' || c >'9'); int x = c - '0'; while (c = getchar(), c >= '0' && c <= '9') x = x * 10 + c - '0'; return x; } void maintain(int o) { //维护区间 sum[o] = sum[lc] + sum[rc]; if (bj[lc] && bj[rc]) bj[o] = 1; //左右都是1，那么该区间也是1 } void build(int o, int l, int r) { //建树 if (l == r) { sum[o] = a[l]; if (sum[o] == 1 || sum[o] == 0) bj[o] = 1; //是0或1就将标记变为1 return; } int mid = l + r >> 1; build(lc, l, mid); build(rc, mid + 1, r); maintain(o); } void modify(int o, int l, int r, int ql, int qr) { //区间修改 if (bj[o]) return; if (l == r) { sum[o] = sqrt(sum[o]); if (sum[o] == 1) bj[o] = 1; //变为了1就将标记改为1 return; } int mid = l + r >> 1; if (ql <= mid) modify(lc, l, mid, ql, qr); if (qr > mid) modify(rc, mid + 1, r, ql, qr); maintain(o); } ll query(int o, int l, int r, int ql, int qr) { //区间查询 if (ql <= l && qr >= r) return sum[o]; int mid = l + r >> 1; ll ans = 0; if (ql <= mid) ans += query(lc, l, mid, ql, qr); if (qr > mid) ans += query(rc, mid + 1, r, ql, qr); return ans; } int main() { n = read(); for (int i = 1; i <= n; ++ i) a[i] = read(); build(1, 1, n); q = read(); while (q --) { int opt = read(), x = read(), y = read(); if (opt == 1) { printf("%lld\n", query(1, 1, n, x, y)); } else { modify(1, 1, n, x, y); } } return 0; }转载于:https://www.cnblogs.com/Gaxc/p/9975604.html
