山东省第五届ACM竞赛

山东省第五届ACM竞赛"/>

山东省第五届ACM竞赛

题目链接

.php?pid=2880

题意 

有连续n个桶，每隔一秒会往所有的桶里各放入一个礼物，取m次，每次取落在该区间内所有桶中的所有礼物，问你m次操作后你会有多少个礼物。（题意进行了抽象，方便理解）

题解

开始打算使用差分数组来做，最后发现不管怎么查分总是不行，然后又想成按时间倒着做，找每个桶最后的覆盖时间，相当于线段染色问题，然后极端情况又会TLE，最终决定还是花点时间打了线段树。
设置两个lazy标记，一个用来标记加和，一个表示是否为0。因为每次都要取完，所以需要设置一lazy来标记该区间被置为 0 。

AC代码

#include<bits/stdc++.h>
#define up(i, x, y) for(ll i = x; i <= y; i++)
#define down(i, x, y) for(ll i = x; i >= y; i--)
#define maxn ((ll)1e5 + 10)
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
ll ans = 0;
struct node
{ll l, r, w, f1, f2; //f2 标记是否为0 ; -1 代表 0, 1 代表正常
}t[maxn * 4 + 1];void build(ll k, ll l, ll r)
{t[k].l = l, t[k].r = r;t[k].f1 = 0;t[k].f2 = 1;t[k].w = 0;if(l == r){return ;}ll m = (l + r) / 2;build(k * 2, l, m);build(k * 2 + 1, m + 1, r);
}void down_(ll k)
{if(t[k].f2 == -1){t[k].f2 = 1;t[k].w = 0;t[k].f1 = 0; // f1与f2 是独立标记的lazy，在当前点不应该清空，// 因为 f2只管当前及以下的节点，而当前点的 f1 // 是由上面影响的，所以不用变/****************************************************************/t[k * 2].f1 = 0;t[k * 2].f2 = -1;t[k * 2].w = 0;t[k * 2 + 1].f1 = 0;t[k * 2 + 1].f2 = -1;t[k * 2 + 1].w = 0;}if(t[k].f1){t[k * 2].f1 += t[k].f1;t[k * 2 + 1].f1 += t[k].f1;t[k * 2].w += (t[k * 2].r - t[k * 2].l + 1) * t[k].f1;t[k * 2 + 1].w += (t[k * 2 + 1].r - t[k * 2 + 1].l + 1) * t[k].f1;t[k].f1 = 0;/*******不要忘记清除*******/}
}
void updata(ll k)//由于是区间 1 - n 更新，所以不必写递归去更新，直接更新根节点就够了
{t[k].f1 += 1;t[k].w += (t[k].r - t[k].l + 1);}void sum(ll k, ll l, ll r)
{if(l <= t[k].l && t[k].r <= r){ans += t[k].w;t[k].f1 = 0;t[k].f2 = -1;t[k].w = 0;return ;}down_(k);ll m = (t[k].l + t[k].r) / 2;if(l <= m) sum(k * 2, l, r);if(r >= m + 1) sum(k * 2 + 1, l ,r);t[k].w = t[k * 2].w + t[k * 2 + 1].w;
}int main()
{ll T; scanf("%lld", &T); while(T--){ll n, m; ans = 0;scanf("%lld %lld", &n, &m);build(1, 1, n);ll pre = 0;while(m--){ll s, x, y; scanf("%lld %lld %lld", &s, &x, &y);if(s - pre > 0){for(ll i = 1; i <= s - pre; i++) //更新多少秒的礼物updata(1);pre = s;}sum(1, x, y);}printf("%lld\n", ans);}
}