SDUT 2880 Devour Magic（线段树lazy和set标记模板）

线段树lazy和set标记模板）"/>

SDUT 2880 Devour Magic（线段树lazy和set标记模板）

题意：给你一个1~n的区间，每过一个单位时间区间值加一

现在有一个操作 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