现在有一个操作 t l r 表示在t时间把 l到r这个区间的的值累加到ans，然后把这段区间清零
思路：以前没做过把一段区间置为某个数的题，涨姿势了，可以和lazy标记类似做一个set标记。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; typedef long long ll; const int maxn = 1e5+5; ll sum[maxn*4], lazy[maxn*4], set[maxn*4], n, q; void pushup(int root, int l, int r) { sum[root] = sum[root*2]+sum[root*2+1]; } void pushdown(int root, int l, int r) { int mid = (l+r)/2; if(set[root] != -1) { lazy[root*2] = lazy[root*2+1] = 0; set[root*2] = set[root*2+1] = set[root]; sum[root*2] = set[root]*(mid-l+1); sum[root*2+1] = set[root]*(r-mid); set[root] = -1; } if(lazy[root]) { lazy[root*2] += lazy[root]; lazy[root*2+1] += lazy[root]; sum[root*2] += lazy[root]*(mid-l+1); sum[root*2+1] += lazy[root]*(r-mid); lazy[root] = 0; } } void Set(int root, int l, int r, int i, int j, ll val) { if(i <= l && j >= r) { set[root] = val; lazy[root] = 0; sum[root] = val*(r-l+1); return ; } pushdown(root, l, r); int mid = (l+r)/2; if(i <= mid) Set(root*2, l, mid, i, j, val); if(j > mid) Set(root*2+1, mid+1, r, i, j, val); pushup(root, l, r); } void update(int root, int l, int r, int i, int j, int val) { if(i <= l && j >= r) { lazy[root] += val; sum[root] += val*(r-l+1); return ; } pushdown(root, l, r); int mid = (l+r)/2; if(i <= mid) update(root*2, l, mid, i, j, val); if(j > mid) update(root*2+1, mid+1, r, i, j, val); pushup(root, l, r); } ll query(int root, int l, int r, int i, int j) { if(i <= l && j >= r) return sum[root]; pushdown(root, l, r); int mid = (l+r)/2; ll res = 0; if(i <= mid) res += query(root*2, l, mid, i, j); if(j > mid) res += query(root*2+1, mid+1, r, i, j); pushup(root, l, r); return res; } int main(void) { int t; cin >> t; while(t--) { memset(lazy, 0, sizeof(lazy)); memset(sum, 0, sizeof(sum)); memset(set, -1, sizeof(set)); scanf("%lld%lld", &n, &q); ll ans = 0; int pre = 0; while(q--) { int t, l, r; scanf("%d%d%d", &t, &l, &r); update(1, 1, n, 1, n, (ll)t-pre); ans += query(1, 1, n, l, r); Set(1, 1, n, l, r, (ll)0); pre = t; } printf("%lld\n", ans); } return 0; } Example Input 1 10 5 1 1 10 2 3 10 3 5 10 4 7 10 5 9 10 Example Output 30
