正文
vijos 1448 校门外的树 （不是05年普及组那题）
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
描述
校门外有很多树，有苹果树，香蕉树，有会扔石头的，有可以吃掉补充体力的……
如今学校决定在某个时刻在某一段种上一种树，保证任一时刻不会出现两段相同种类的树，现有两个操作：
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输出一个答案
样例1样例输入1
5 4
1 1 3
2 2 5
1 2 4
2 3 5
样例输出1
1
2
限制
1s
提示
范围：20%的数据保证，n,m<=100
60%的数据保证，n <=1000,m<=50000
100%的数据保证，n,m<=50000
来源
dejiyu@CSC WorkGroup
这道题是典型的区间问题
但由于树的种类比较多，直接维护可能会超时
于是就用括号序列来做 。
比方说[2,10] 种树 在2 放一个左括号，10放一个右括号
统计[2,10]内有多少树的话，就找[2,10]内左括号的数量减去[1,2]内右括号的数量
屠龙宝刀点击就送
#include <cstring>
#include <cstdio>typedef long long LL;
struct tree
{
LL l,r;
LL zk,yk;
}t[*+];
LL n,m,ans;
void build(LL k,LL l,LL r)
{
t[k].l=l;t[k].r=r;
if(l==r) return;
LL mid=(l+r)>>;
build(k<<,l,mid);
build(k<<|,mid+,r);
}
void ptz(LL l,LL k)
{
if(t[k].l==l&&t[k].r==l) t[k].zk++;
else
{
LL mid=(t[k].l+t[k].r)>>;
if(l>mid) ptz(l,k<<|);
else if(l<=mid) ptz(l,k<<);
t[k].zk=t[k<<].zk+t[k<<|].zk;
}
}
void pty(LL l,LL k)
{
if(t[k].l==l&&t[k].r==l) t[k].yk++;
else
{
LL mid=(t[k].l+t[k].r)>>;
if(l>mid) pty(l,k<<|);
else if(l<=mid) pty(l,k<<);
t[k].yk=t[k<<].yk+t[k<<|].yk;
}
}
LL queryz(LL l,LL r,LL k)
{
if(t[k].l>=l&&t[k].r<=r) return t[k].zk;
LL mid=(t[k].l+t[k].r)>>;
if(r<=mid) return queryz(l,r,k<<);
else if(l>mid) return queryz(l,r,k<<|);
else return queryz(l,mid,k<<)+queryz(mid+,r,k<<|);
}
LL queryy(LL l,LL r,LL k)
{
if(t[k].l>=l&&t[k].r<=r) return t[k].yk;
LL mid=(t[k].l+t[k].r)>>;
if(r<=mid) return queryy(l,r,k<<);
else if(l>mid) return queryy(l,r,k<<|);
else return queryy(l,mid,k<<)+queryy(mid+,r,k<<|);
}
void qr(LL &x)
{
x=;bool f=;
char ch=getchar();
while(ch>''||ch<'')
{
if(ch=='-') f=;
ch=getchar();
}
while(ch>=''&&ch<='')
{
x=x*+(int)ch-;
ch=getchar();
}
x=(f==)?((~x)+):x;
}
int main()
{
qr(n);qr(m);
build(,,n);
for(LL x,y,z;m--;)
{
qr(x);qr(y);qr(z);
if(x==) ptz(y,),pty(z,);
else
{
LL ans=queryz(,z,);
if(y!=)
ans-=queryy(,y-,);
printf("%lld\n",ans);
}
}
return ;
}
