P2184 贪婪大陆

题目背景

面对蚂蚁们的疯狂进攻，小\(FF\)的\(Tower\) \(defence\)宣告失败……人类被蚂蚁们逼到了\(Greed\) \(Island\)上的一个海湾。现在，小\(FF\)的后方是一望无际的大海， 前方是变异了的超级蚂蚁。 小\(FF\)还有大好前程，他可不想命丧于此， 于是他派遣手下最后一批改造\(SCV\)布置地雷以阻挡蚂蚁们的进攻。

题目描述

小\(FF\)最后一道防线是一条长度为\(N\)的战壕， 小\(FF\)拥有无数多种地雷，而SCV每次可以在\([L,R]\)区间埋放同一种不同于之前已经埋放的地雷。 由于情况已经十万火急，小\(FF\)在某些时候可能会询问你在\([L',R']\)区间内有多少种不同的地雷， 他希望你能尽快的给予答复。

输入输出格式

输入格式：

第一行为两个整数\(n\)和\(m\)； \(n\)表示防线长度，\(m\)表示\(SCV\)布雷次数及小\(FF\)询问的次数总和。

接下来有\(m\)行， 每行三个整数\(Q\),\(L\),\(R\)； 若\(Q\)=1则表示\(SCV\)在\([L,R]\)这段区间布上一种地雷， 若\(Q=2\)则表示小\(FF\)询问当前\([L,R]\)区间总共有多少种地雷。

输出格式：

对于小FF的每次询问，输出一个答案（单独一行），表示当前区间地雷总数。

说明：

对于30%的数据： \(0<=n, m<=1000\);

对于100%的数据：\(0<=n, m<=10^5\).

---

说两个方法吧

方法一：维护区间和和合并区间时多加上的一部分，基于容斥原理，是这位大佬想到的

具体的：
我们维护\(sum\)代表这个区间的种类数，每次区间修改操作即为对二进制所划分的每个区间+1（不是对每个值，是对区间），防止退化我们用一个\(lazy1\)维护

这时候在区间合并的时候就会产生问题，会重复统计。

我们再维护一个值\(mer\)代表这个二进制区间被多少次划分时分开了，则统计答案时即为\(sum[ls]+sum[rs]-mer[ls]\)

这个也是区间操作，同样用一个\(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; }

方法二：维护区间两端进行统计

我们发现，对于一个区间\(1\)~\(i\)，\(i\)及其左边的区间的左端点的数量即为答案

对于一个区间\(i\)~\(n\)，\(i\)左边的右端点不是它的答案

综合一下，对于一个区间\(l\)~\(r\)，\(r\)及左边的左端点数量-\(l\)左边的右端点数量，不就是\(l\)~\(r\)所覆盖的区间数量了吗？

单点修改，我们只需要用两个树状数组维护就行了

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

转载于:https://www.cnblogs.com/butterflydew/p/9299948.html

总结

以上是生活随笔为你收集整理的洛谷 P2184 贪婪大陆 解题报告的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。