P2184 貪婪大陸

題目背景

面對螞蟻們的瘋狂進攻，小\(FF\)的\(Tower\) \(defence\)宣告失敗……人類被螞蟻們逼到了\(Greed\) \(Island\)上的一個海灣。現(xiàn)在，小\(FF\)的后方是一望無際的大海， 前方是變異了的超級螞蟻。 小\(FF\)還有大好前程，他可不想命喪于此， 于是他派遣手下最后一批改造\(SCV\)布置地雷以阻擋螞蟻們的進攻。

題目描述

小\(FF\)最后一道防線是一條長度為\(N\)的戰(zhàn)壕， 小\(FF\)擁有無數(shù)多種地雷，而SCV每次可以在\([L,R]\)區(qū)間埋放同一種不同于之前已經(jīng)埋放的地雷。 由于情況已經(jīng)十萬火急，小\(FF\)在某些時候可能會詢問你在\([L',R']\)區(qū)間內(nèi)有多少種不同的地雷， 他希望你能盡快的給予答復(fù)。

輸入輸出格式

輸入格式：

第一行為兩個整數(shù)\(n\)和\(m\)； \(n\)表示防線長度，\(m\)表示\(SCV\)布雷次數(shù)及小\(FF\)詢問的次數(shù)總和。

接下來有\(m\)行， 每行三個整數(shù)\(Q\),\(L\),\(R\)； 若\(Q\)=1則表示\(SCV\)在\([L,R]\)這段區(qū)間布上一種地雷， 若\(Q=2\)則表示小\(FF\)詢問當(dāng)前\([L,R]\)區(qū)間總共有多少種地雷。

輸出格式：

對于小FF的每次詢問，輸出一個答案（單獨一行），表示當(dāng)前區(qū)間地雷總數(shù)。

說明：

對于30%的數(shù)據(jù)： \(0<=n, m<=1000\);

對于100%的數(shù)據(jù)：\(0<=n, m<=10^5\).

---

說兩個方法吧

方法一：維護區(qū)間和和合并區(qū)間時多加上的一部分，基于容斥原理，是這位大佬想到的

具體的：
我們維護\(sum\)代表這個區(qū)間的種類數(shù)，每次區(qū)間修改操作即為對二進制所劃分的每個區(qū)間+1（不是對每個值，是對區(qū)間），防止退化我們用一個\(lazy1\)維護

這時候在區(qū)間合并的時候就會產(chǎn)生問題，會重復(fù)統(tǒng)計。

我們再維護一個值\(mer\)代表這個二進制區(qū)間被多少次劃分時分開了，則統(tǒng)計答案時即為\(sum[ls]+sum[rs]-mer[ls]\)

這個也是區(qū)間操作，同樣用一個\(lazy2\)來維護

Code:

#include <cstdio> #define ls id<<1 #define rs id<<1|1 const int N=100010; int sum[N<<2],mer[N<<2],lazy1[N<<2],lazy2[N<<2],n,m; void push_down(int id,int l,int r) {if(l!=r){sum[ls]+=lazy1[id];sum[rs]+=lazy1[id];mer[ls]+=lazy2[id];lazy1[ls]+=lazy1[id];lazy1[rs]+=lazy1[id];lazy2[ls]+=lazy2[id];lazy2[rs]+=lazy2[id];}lazy1[id]=lazy2[id]=0; } void change(int id,int l,int r,int L,int R) {if(l==L&&r==R){sum[id]++;lazy1[id]++;lazy2[id]++;return;}int Mid=L+R>>1;if(r<=Mid)change(ls,l,r,L,Mid);else if(l>Mid)change(rs,l,r,Mid+1,r);else{mer[ls]++;change(ls,l,Mid,L,Mid);change(rs,Mid+1,r,Mid+1,R);}push_down(id,L,R);sum[id]=sum[ls]+sum[rs]-mer[ls]; } int query(int id,int l,int r,int L,int R) {push_down(id,L,R);if(l==L&&r==R)return sum[id];int Mid=L+R>>1;if(r<=Mid)return query(ls,l,r,L,Mid);else if(l>Mid)return query(rs,l,r,Mid+1,r);elsereturn query(ls,l,Mid,L,Mid)+query(rs,Mid+1,r,Mid+1,R)-mer[ls]; } int main() {scanf("%d%d",&n,&m);int q,l,r;for(int i=1;i<=m;i++){scanf("%d%d%d",&q,&l,&r);if(q==1) change(1,l,r,1,n);else printf("%d\n",query(1,l,r,1,n));}return 0; }

方法二：維護區(qū)間兩端進行統(tǒng)計

我們發(fā)現(xiàn)，對于一個區(qū)間\(1\)~\(i\)，\(i\)及其左邊的區(qū)間的左端點的數(shù)量即為答案

對于一個區(qū)間\(i\)~\(n\)，\(i\)左邊的右端點不是它的答案

綜合一下，對于一個區(qū)間\(l\)~\(r\)，\(r\)及左邊的左端點數(shù)量-\(l\)左邊的右端點數(shù)量，不就是\(l\)~\(r\)所覆蓋的區(qū)間數(shù)量了嗎？

單點修改，我們只需要用兩個樹狀數(shù)組維護就行了

Code:

#include <cstdio> const int N=100010; int s[2][N],n,m; int query(int typ,int x) {int sum=0;while(x){sum+=s[typ][x];x-=x&-x;}return sum; } void add(int typ,int x) {while(x<=n){s[typ][x]+=1;x+=x&-x;} } int main() {scanf("%d%d",&n,&m);int q,l,r;for(int i=1;i<=m;i++){scanf("%d%d%d",&q,&l,&r);if(q==1)add(0,l),add(1,r);elseprintf("%d\n",query(0,r)-query(1,l-1));}return 0; }

---

2018.7.12

轉(zhuǎn)載于:https://www.cnblogs.com/butterflydew/p/9299948.html

總結(jié)

以上是生活随笔為你收集整理的洛谷 P2184 贪婪大陆 解题报告的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。