nyoj 1217 GLaDOS的耳机

3000ms | 内存限制： 65535

GLaDOS是耳机控制。对他来说，听到供电设备是水电、核电还是火电已经不满足了。GLaDOS有更大的目标，他想听到宇宙中最神秘的代号是“Y_A_FL"的声音。GLaDOS决定升级他的耳机，以实现这一目标。但是笨手笨脚的GLaDOS说，加工升级神马太难了。所以GLaDOS想让JX为他解决这个问题，而JX又把这个问题给了你。你能帮这两个二货解决这个问题吗？ 现在，给你一个n点，说明耳机上有n点，相邻的每两点间距为1单位长度。从左到右，每个点的编号分别为1、2、3...n。GLaDOS想要m次操作这条耳机线。GLaDOS有两种操作： ⊙ 1 L R c D代表GLaDOS想在这个耳机线从L点到R点的范围内涂一层金属漆(1<=L,R<=n)金属漆的颜色是c(0<=c<=新涂的金属漆将覆盖原有的金属漆，每单位长度的金属漆重量为d(0<d<=1000)(原耳机线重量为0，无色)。 ⊙2 L R代表GLaDOS想知道从L点到R点的耳机线的重量。

M次操作结束后，GLaDOS想知道这个耳机线的总重量和这个耳机线的颜色数量。

多组数据(最多11组)包含输入

每组数据的第一行是两个整数n，m(2<=n,m<=80000)分别表示耳机长度和GLADOS操作次数。

然后是m行，每行一个操作。

输出 每组数据

对于每个操作2，您将输出一个整数，代表L到R范围内耳机线的重量。

每组数据的最后一行，输出耳机的总重量和颜色数量。

样例输入

1000 61 100 1000 1 102 500 6211 7 842 2 102 500 6211 100 347 3 232 120 217

样例输出

12102420417123031 3

提示

数据量不小，建议使用scanf()输入

解题思路:输出重量是典型的线段树区间求和。以下是如何寻求颜色的类型。在这里，我们仍然使用线段树。我们知道未来添加的颜色越多，我们有权选择，也就是说，我们可以覆盖以前的颜色，所以我们可以倒过来添加颜色，然后添加这个范围1。只要某种颜色找不到可以添加1的位置，颜色就会被覆盖。这里需要注意的是，要打开long long，否则WA。。。

#include<iostream>#include<cstdio>#include<cstring>using namespace std;typedef long long LL;const int maxn = 80005;struct Seg{int l,r;LL sum,lazy;}tree[2][maxn<<2];struct Node{int l,r,c;}color[maxn];int n,m,cnt;bool vis[40005],done;void build(int rt,int l,int r){tree[0][rt].l = l, tree[0][rt].r = r;tree[1][rt].l = l, tree[1][rt].r = r;tree[0][rt].sum = tree[0][rt].lazy = 0;tree[1][rt].sum = tree[1][rt].lazy = 0;if(l + 1 == r) return;int mid = (l + r) >> 1;build(rt<<1,l,mid);build(rt<<1|1,mid,r);}void PushDown(int rt){if(tree[0][rt].lazy){tree[0][rt<<1].lazy += tree[0][rt].lazy;tree[0][rt<<1].sum += (tree[0][rt<<1].r - tree[0][rt<<1].l) * tree[0][rt].lazy;tree[0][rt<<1|1].lazy += tree[0][rt].lazy;tree[0][rt<<1|1].sum += (tree[0][rt<<1|1].r - tree[0][rt<<1|1].l) * tree[0][rt].lazy;tree[0][rt].lazy = 0;}}void update(int rt,int l,int r,int val){if(l <= tree[0][rt].l && tree[0][rt].r <= r){tree[0][rt].sum += (tree[0][rt].r - tree[0][rt].l) * val;tree[0][rt].lazy += val;return;}PushDown(rt);int mid = (tree[0][rt].l + tree[0][rt].r) >> 1;if(l < mid) update(rt<<1,l,r,val);if(mid < r) update(rt<<1|1,l,r,val);tree[0][rt].sum = tree[0][rt<<1].sum + tree[0][rt<<1|1].sum;}void update(int rt,int l,int r){if(tree[1][rt].sum == tree[1][rt].r - tree[1][rt].l) return;if(l <= tree[1][rt].l && tree[1][rt].r <= r){tree[1][rt].sum = tree[1][rt].r - tree[1][rt].l;done = true;return;}int mid = (tree[1][rt].l + tree[1][rt].r) >> 1;if(l < mid) update(rt<<1,l,r);if(mid < r) update(rt<<1|1,l,r);tree[1][rt].sum = tree[1][rt<<1].sum + tree[1][rt<<1|1].sum;}LL query(int rt,int l,int r){if(l <= tree[0][rt].l && tree[0][rt].r <= r)return tree[0][rt].sum;PushDown(rt);LL ans = 0;int mid = (tree[0][rt].l + tree[0][rt].r) >> 1;if(l < mid) ans += query(rt<<1,l,r);if(mid < r) ans += query(rt<<1|1,l,r);return ans;}int main(){int op,l,r,c,d;while(scanf("%d %d",&n,&m)!=EOF){build(1,1,n);cnt = 0;memset(vis,false,sizeof(vis));while(m--){scanf("%d %d %d",&op,&l,&r);if(op == 1){scanf("%d %d",&c,&d);update(1,l,r,d);color[++cnt].l = l, color[cnt].r = r;color[cnt].c = c;}else printf("%lld\n",query(1,l,r));}int ans = 0;for(int i = cnt; i >= 1; i--){done = false;update(1,color[i].l,color[i].r);if(vis[color[i].c] == false){if(done == true) {ans++;vis[color[i].c] = true;}}}printf("%lld %d\n",tree[0][1].sum,ans);}return 0;}