生活随笔
收集整理的這篇文章主要介紹了
nyoj 1217 GLaDOS的耳机
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
GLaDOS的耳機 時間限制：
3000 ?ms ?|? 內存限制：
65535 ?KB 難度：
4
描述
????????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<=40000) ，新涂的金屬漆會將原有的金屬漆覆蓋，每單位長度的金屬漆重量為d(0<d<=1000) （最初耳機線的重量為0 ，沒有顏色）。 ⊙?2 L R ? 代表著GLaDOS 想要知道耳機線在L點 到R點 這段區間內的重量。
? 在 m 次操作結束之后，GLaDOS 想知道這根耳機線的總重量和這根耳機線上顏色的種數。
輸入包含多組數據（最多11組） 輸出每組數據 樣例輸入 1000 6
1 100 1000 1 10
2 500 621
1 7 842 2 10
2 500 621
1 100 347 3 23
2 120 217
樣例輸出 1210
2420
4171
23031 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;
}
總結
以上是生活随笔 為你收集整理的nyoj 1217 GLaDOS的耳机 的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔 網站內容還不錯，歡迎將生活随笔 推薦給好友。
