「JoyOI1473」校门外的树3
描述 Description
校门外有很多树，有苹果树，香蕉树，有会扔石头的，有可以吃掉补充体力的……
如今学校决定在某个时刻在某一段种上一种树，保证任一时刻不会出现两段相同种类的树，现有两个操作：
K=1，读入l,r表示在l~r之间种上的一种树
K=2，读入l,r表示询问l~r之间能见到多少种树
（l,r>0）
输入格式 InputFormat
第一行n,m表示道路总长为n，共有m个操作
接下来m行为m个操作
输出格式 OutputFormat
对于每个k=2输出一个答案
题解
将[a,b]种上一种树
这个修改操作影响的询问满足，询问区间与[a,b]有交，转化为统计总修改数-与某询问交为空集的修改数
对于一个修改操作[l,r]，与它为空集的询问[a,b]满足a∈[1,l-1]或者b∈[r+1,n]
用两棵线段树维护
修改[l,r]，将第一棵的[1,l-1]区间+1，第二棵[r+1,n]区间+1
询问[a,b]，答案为之前的修改数-（第一棵单点询问b+第二棵单点询问a）
代码中线段树结点的l，r其实就是两棵线段树。。。
标记永久化
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 |
#include<cstdio> #include<iostream> using namespace std; int n,m; struct data{ int l,r; int left,right; }tr[200001]; void build(int k,int s,int t) { tr[k].left=s;tr[k].right=t; if(s==t)return; int mid=(s+t)>>1; build(k<<1,s,mid); build(k<<1|1,mid+1,t); } void insertl(int k,int x,int y) { int l=tr[k].left,r=tr[k].right; if(l==x&&y==r){tr[k].l++;return;} int mid=(l+r)>>1; if(y<=mid)insertl(k<<1,x,y); else if(x>mid)insertl(k<<1|1,x,y); else { insertl(k<<1,x,mid); insertl(k<<1|1,mid+1,y); } } void insertr(int k,int x,int y) { int l=tr[k].left,r=tr[k].right; if(l==x&&y==r){tr[k].r++;return;} int mid=(l+r)>>1; if(y<=mid)insertr(k<<1,x,y); else if(x>mid)insertr(k<<1|1,x,y); else { insertr(k<<1,x,mid); insertr(k<<1|1,mid+1,y); } } int askl(int k,int x) { int l=tr[k].left,r=tr[k].right; if(l==r)return tr[k].l; int mid=(l+r)>>1; if(x<=mid)return tr[k].l+askl(k<<1,x); else return tr[k].l+askl(k<<1|1,x); } int askr(int k,int x) { int l=tr[k].left,r=tr[k].right; if(l==r)return tr[k].r; int mid=(l+r)>>1; if(x<=mid)return tr[k].r+askr(k<<1,x); else return tr[k].r+askr(k<<1|1,x); } int main() { int total=0,ans; scanf("%d%d",&n,&m); build(1,0,n); for(int i=1;i<=m;i++) { int t,a,b; scanf("%d%d%d",&t,&a,&b); if(t==1){ insertl(1,0,a-1); insertr(1,b+1,n); total++; } else { ans=askr(1,a)+askl(1,b); printf("%d\n",total-ans); } } return 0; } |
计数器 9856407
OI 课件=>
OI 课件=>
黄学长，建立插入的补集时右端不是应该建立到（b+1,n+1）吗？？？如果这样，插入到n中，b+1>n就会爆炸。。。虽说没这个数据。。。
黄学长..答案应该是 [之前的修改数 – (第一棵单点询问b + 第二棵单点询问a)] 吧..
就是在左树中找右端点,右树中找左端点吧..
是的。。。
请问大神，此题您的程序中的tr
.l和tr 
.r是什么意思呢？
在题解中增加了说明