首页 > 代码库 > vijos P1448 校门外的树
vijos P1448 校门外的树
描述
校门外有很多树，有苹果树，香蕉树，有会扔石头的，有可以吃掉补充体力的……
如今学校决定在某个时刻在某一段种上一种树，保证任一时刻不会出现两段相同种类的树，现有两个操作：
K=1，K=1，读入l、r表示在区间[l,r]中种上一种树，每次操作种的树的种类都不同
K=2，读入l,r表示询问l~r之间能见到多少种树（l,r>0）
输入格式
第一行n,m表示道路总长为n，共有m个操作
接下来m行为m个操作
输出格式
对于每个k=2输出一个答案
提示
范围：20%的数据保证，n,m<=100
60%的数据保证，n <=1000,m<=50000
100%的数据保证，n,m<=50000
由于这两天BZOJ炸了，于是准备上vijos刷点题……然后发现刷不动……我好弱啊……
由于这道题想了半天不会做，被嘲讽数据结构学傻了……好吧，这几天我整天整天的不在状态
好吧，我还是来讲一下写法(其实这道题的在vijos上就有非常详细的讲解了)。这道题目大意就是给出一些区间，每次询问一个区间和多少个区间有交。
然后，一个区间和另一个区间有交，当且仅当那个区间的左端点或者右端点在这个区间里。于是，我们就可以令ai表示前i个点共出现了多少个区间左端点，bi表示出现了多少个右端点。这两个东西用树状数组维护即可。询问区间[l,r]的答案就是ar-bl-1。
下面贴代码：
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)#define maxn 50010using namespace std;typedef long long llg;int c1[maxn],c2[maxn];int n,m;int getint(){ int w=0;bool q=0; char c=getchar(); while((c>‘9‘||c<‘0‘)&&c!=‘-‘) c=getchar(); if(c==‘-‘) c=getchar(),q=1; while(c>=‘0‘&&c<=‘9‘) w=w*10+c-‘0‘,c=getchar(); return q?-w:w;}void add1(int x,int y){while(x<=n) c1[x]+=y,x+=x&(-x);}void add2(int x,int y){while(x<=n) c2[x]+=y,x+=x&(-x);}int sum1(int x){ int t=0; while(x) t+=c1[x],x-=x&(-x); return t;}int sum2(int x){ int t=0; while(x) t+=c2[x],x-=x&(-x); return t;}int main(){ File("a"); n=getint(); m=getint(); while(m--){ int ty=getint(),l,r; l=getint();r=getint(); if(ty==1) add1(l,1),add2(r,1); else printf("%d\n",sum1(r)-sum2(l-1)); }}vijos P1448 校门外的树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。