题意
题目链接
sol
传说中的吉司机线段树？？感觉和bzoj冒险那题差不多，就是强行剪枝。。。
这题最坑的地方在于对于操作1，$c >= 0$, 操作2中需要对0取max，$a[i] >= 0$，这不就是统计最小值出现的次数么？？
按照套路
维护好区间赋值标记 / 区间加法标记 / 区间max标记 / 区间最小值 / 区间最小值出现的次数 / 区间次小值
对于第二个操作就拆成区间加 和 区间max
区间max是一个很神奇的操作
设当前加入的数为val
若val>=mn，那该操作对该区间无影响
若se < val < mn，该操作只会对次小值产生影响，因为对其他的标记均不会产生影响，因此打一个额外的标记即可
否则暴力递归
时间复杂度：$o(n log^2n)$??
另外这东西可以做区间加 / 查询历史版本，前者维护一下标记就行，，后者嘛，，，等长大了再研究吧qwq
#include<cstdio> #include<algorithm> #define ll long long //#define int long long using namespace std; const int maxn = 3 * 1e5 + 10; const ll inf = 1e10 +10; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } #define ls k << 1 #define rs k << 1 | 1 int n, q; int a[maxn]; struct node { int l, r, siz, cnt; ll mx, add, mn, se, cov; }t[maxn << 2]; void update(int k) { //t[k].mn = min(t[ls].mn, t[rs].mn); if(t[ls].mn < t[rs].mn) t[k].cnt = t[ls].cnt, t[k].mn = t[ls].mn, t[k].se = min(t[rs].mn, t[ls].se); else if(t[ls].mn > t[rs].mn) t[k].cnt = t[rs].cnt, t[k].mn = t[rs].mn, t[k].se = min(t[ls].mn, t[rs].se); else t[k].cnt = t[ls].cnt + t[rs].cnt, t[k].mn = t[ls].mn, t[k].se = min(t[ls].se, t[rs].se); } void memp(int k, ll val) { t[k].cov = val; t[k].cnt = t[k].siz; t[k].se = inf; t[k].mx = -inf; t[k].add = 0; t[k].mn = val; } void addp(int k, ll val) { if(t[k].se != inf) t[k].se += val; if(t[k].mx != -inf) t[k].mx += val; t[k].mn += val; t[k].add += val; } void maxp(int k, ll val) { t[k].mn = max(t[k].mn, val);// t[k].mx = max(t[k].mx, val); } void pushdown(int k) { if(t[k].cov != inf) memp(ls, t[k].cov), memp(rs, t[k].cov), t[k].cov = inf; if(t[k].add) addp(ls, t[k].add), addp(rs, t[k].add), t[k].add = 0; if(t[k].mx != -inf) maxp(ls, t[k].mx), maxp(rs, t[k].mx), t[k].mx = -inf; } void build(int k, int ll, int rr) { t[k] = (node) {ll, rr, rr - ll + 1, 0, -inf, 0, 0, inf, inf}; if(ll == rr) { t[k].mn = a[ll]; t[k].cnt = 1; return ; } int mid = t[k].l + t[k].r >> 1; build(ls, ll, mid); build(rs, mid + 1, rr); update(k); } void intmem(int k, int ll, int rr, ll val) { if(ll <= t[k].l && t[k].r <= rr) {memp(k, val); return ;} pushdown(k); int mid = t[k].l + t[k].r >> 1; if(ll <= mid) intmem(ls, ll, rr, val); if(rr > mid) intmem(rs, ll, rr, val); update(k); } void intadd(int k, int ll, int rr, ll val) { if(ll <= t[k].l && t[k].r <= rr) {addp(k, val); return ;} pushdown(k); int mid = t[k].l + t[k].r >> 1; if(ll <= mid) intadd(ls, ll, rr, val); if(rr > mid) intadd(rs, ll, rr, val); update(k); } void intmax(int k, int ll, int rr, ll val) { if(val <= t[k].mn) return ; if(ll <= t[k].l && t[k].r <= rr && t[k].se > val) {//tag maxp(k, val); return ; } int mid = t[k].l + t[k].r >> 1; pushdown(k); if(ll <= mid) intmax(ls, ll, rr, val); if(rr > mid) intmax(rs, ll, rr, val); update(k); } ll query(int k, int ll, int rr) { // int ans = 0; if(ll <= t[k].l && t[k].r <= rr) return (t[k].mn == 0 ? t[k].cnt : 0); pushdown(k); int mid = t[k].l + t[k].r >> 1; if(ll > mid) return query(rs, ll, rr); else if(rr <= mid) return query(ls, ll, rr); else return query(ls, ll, rr) + query(rs, ll, rr); } main() { // freopen("4355.in", "r", stdin); // freopen("4355.out", "w", stdout); n = read(); q = read(); for(int i = 1; i <= n; i++) a[i] = read(); build(1, 1, n); while(q--) { int opt = read(), l = read(), r = read(), val; if(opt == 3) printf("%dn", query(1, l, r)); else { val = read(); if(opt == 1) intmem(1, l, r, val); else { intadd(1, l, r, val); intmax(1, l, r, 0); } } } return 0; }
本文来自网络收集，不代表计算机技术网立场，如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址：https://www.ctvol.com/c-cdevelopment/607774.html