题意：
有n个格子，一开始全部面向top。接下来的每次修改F a b ，如果 a>b则将a~b之间的格子全面置为向右，否则置为向左。对于每个询问Q输出向左、top、右的数量。
思路：
普通线段树。每个结点中保存三个值，分别对应3个方向的数量。要设置一下lazy_tag以减少时间消耗，因为有可能Q远少于F，那么一直在更改，大多可能不需要改到，暂时不更新，询问时要用到再更新。每次一改就整个区间都是一个方向，所以当有tag时可以往下推各占多少。
#include<bits/stdc++.h>
using namespace std;
int ans[];//答案
struct node
{
bool tag;
int num[];
node *ll,*rr;
node()
{
tag=false;
num[]=num[]=num[]=;
ll=rr=;
}
}; node * built(int LL, int RR)
{
node *tmp=new(node);
if(LL==RR)
{
tmp->num[]=;
return tmp;
}
int mid=(LL+RR)>>;
tmp->ll=built(LL,mid);
tmp->rr=built(mid+,RR);
tmp->num[]+=tmp->ll->num[]+tmp->rr->num[]; //开始只需要更新向上的
return tmp;
} void modify( node *t,int LL,int RR,int mid)//专门修改统计数量
{
if(t->num[])
{
t->ll->num[]=mid+-LL;
t->ll->num[]=t->ll->num[]=;
t->rr->num[]=RR-mid;
t->rr->num[]=t->rr->num[]=;
}
if(t->num[])
{
t->ll->num[]=mid+-LL;
t->ll->num[]=t->ll->num[]=;
t->rr->num[]=RR-mid;
t->rr->num[]=t->rr->num[]=;
}
if(t->num[])
{
t->ll->num[]=mid+-LL;
t->ll->num[]=t->ll->num[]=;
t->rr->num[]=RR-mid;
t->rr->num[]=t->rr->num[]=;
}
} void update(int ll,int rr,int LL,int RR,int c,node *t)
{
if(ll==LL&&rr==RR)
{
t->tag=true;
if(c==)
{
t->num[]=RR-LL+;
t->num[]=t->num[]=;
}
else
{
t->num[]=RR-LL+;
t->num[]=t->num[]=;
}
return;
}
int mid=(LL+RR)>>; if(t->tag)
{
t->tag=false;
t->ll->tag=t->rr->tag=true;
modify(t,LL,RR,mid);
}
if(ll>mid) //右边
update(ll,rr,mid+,RR,c,t->rr);
else if(rr<=mid) //左边
update(ll,rr,LL,mid,c,t->ll);
else
{
update(ll, mid, LL, mid, c,t->ll);
update(mid+,rr,mid+,RR,c,t->rr);
}
t->num[]=t->ll->num[]+t->rr->num[];
t->num[]=t->ll->num[]+t->rr->num[];
t->num[]=t->ll->num[]+t->rr->num[];
} void query(int ll,int rr,int LL,int RR,node* t)
{
if(ll==LL && rr==RR)
{
ans[]+=t->num[];
ans[]+=t->num[];
ans[]+=t->num[];
return;
}
int mid=((LL+RR)>>);
if(t->tag)
{
t->tag=false;
t->ll->tag= t->rr->tag= true;
modify(t, LL, RR, mid);
} if(ll>mid) query(ll,rr,mid+,RR,t->rr);
else if(rr<=mid) query(ll,rr,LL,mid,t->ll);
else
{
query(ll, mid, LL, mid, t->ll);
query(mid+,rr,mid+,RR,t->rr);
} } int main()
{
//freopen("e://input.txt","r",stdin);
int a, t, e, r;
char ch; while(cin>>a>>t)
{
node *tree=built(,t); //建树 for(int i=; i<a; i++)
{
cin>>ch;
scanf("%d %d", &e, &r);
if(ch=='F') //修改
{
if(e>r) update(r, e, , t, , tree);
else update(e, r, , t, , tree);
}
else //Q 查询
{
memset(ans,,sizeof(ans));
query(e,r,,t,tree);
printf("%d %d %d\n",ans[],ans[],ans[]);
}
}
}
return ;
}
AC代码