NBUT 1120 线段树

input

q n

q行 F a b或者Q a b

output

face left  face top  face right

可以用map或者线段树做

 //map
#include<cstdio>
#include<map>
using namespace std;
map<int, char>a;
int main()
{
int n, t, i, d2, d1, r, l, s;
char com;
map<int, char>::iterator p, q;
while (~scanf("%d%d", &n, &t))
{
a.insert(make_pair(, 't'));
a.insert(make_pair(, 't'));
a.insert(make_pair(t + , 't'));
for (i = ; i < n; i++)
{
scanf("\n%c%d%d", &com, &d1, &d2);
if (com == 'F')
{
if (d1 > d2)
{
com = 'l';
for (p = a.begin(); p->first < d2; p++);
for (q = p; q->first <= d1; q++);
q--;
char tmp;
tmp = q->second;
q++;
if (p != q) a.erase(p, q);
a.insert(make_pair(d2, com));
a.insert(make_pair(d1 + , tmp));
}
else
{
com = 'r';
for (p = a.begin(); p->first < d1; p++);
for (q = p; q->first <= d2; q++);
q--;
char tmp;
tmp = q->second;
q++;
if (p != q) a.erase(p, q);
a.insert(make_pair(d1, com));
a.insert(make_pair(d2 + , tmp));
}
}
else
{
r = ; l = ; s = ;
for (p = a.begin(); p->first <= d1; p++);
for (q = p; q->first <= d2; q++);
q--;
p--;
for (; p != q;)
{
if (p->second == 'r')
r += (++p)->first - d1;
else if (p->second == 'l')
l += (++p)->first - d1;
else s += (++p)->first - d1;
d1 = p->first;
}
if (q->second == 'r') r += d2 - d1 + ;
else if (q->second == 'l') l += d2 - d1 + ;
else s += d2 - d1 + ;
printf("%d %d %d\n", l, s, r);
}
}
a.clear();
}
return ;
}
 #include <cstdio>
#include <queue>
#include <cstring>
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <ctime>
#include <cmath>
#define MAX 100000
using namespace std;
int q,n,setv[MAX*],v,a,b,sum[],sumv[MAX*][];
void pushdown(int &l,int &r,int &k)
{
if(setv[k]<) return;
int m=l+((r-l)>>),lc=k<<,rc=(k<<)+;
setv[rc]=setv[lc]=setv[k];
memset(sumv[lc],,sizeof(sumv[]));
memset(sumv[rc],,sizeof(sumv[]));
sumv[lc][setv[k]]=m-l+;
sumv[rc][setv[k]]=r-m;
setv[k]=-;
}
void reset(int l,int r,int k)
{
int lc=k<<,rc=(k<<)+;
sumv[k][]=sumv[lc][]+sumv[rc][];
sumv[k][]=sumv[lc][]+sumv[rc][];
sumv[k][]=sumv[lc][]+sumv[rc][];
}
void update(int l,int r,int k)
{
int lc=k<<,rc=(k<<)+;
if(a<=l&&b>=r)
{
setv[k]=v;
memset(sumv[k],,sizeof(sumv[]));
sumv[k][setv[k]]=r-l+;
return;
}
pushdown(l,r,k);
int m=l+((r-l)>>);
if(a<=m) update(l,m,lc);
if(b>m) update(m+,r,rc);
reset(l,r,k);
}
void query(int l,int r,int k)
{
// printf("%d:%d %d %d %d\n",k,setv[k],sumv[k][0],sumv[k][1],sumv[k][2]);
if(setv[k]>=)
{
sum[setv[k]]+=min(r,b)-max(l,a)+;
return;
}
if(a<=l&&b>=r)
{
sum[]+=sumv[k][];
sum[]+=sumv[k][];
sum[]+=sumv[k][];
return;
}
int m=l+((r-l)>>);
if(a<=m) query(l,m,k<<);
if(b>m) query(m+,r,(k<<)+);
}
int main()
{
//freopen("/home/user/桌面/in","r",stdin);
while(scanf("%d%d",&q,&n)==)
{
memset(setv,-,sizeof(setv[])**n);
memset(sumv,,sizeof(sumv[])**n);
a=;b=n;v=;
update(,n,);
char op[];
while(q--)
{
scanf("%s%d%d",op,&a,&b);
if(op[]=='F')
{
v=;
if(a>b)
{
v=;
swap(a,b);
}
update(,n,);
// for(int i=1;i<3*n;i++) printf("%d:%d %d %d %d\n",i,setv[i],sumv[i][0],sumv[i][1],sumv[i][2]);
}
else
{
sum[]=sum[]=sum[]=;
query(,n,);
printf("%d %d %d\n",sum[],sum[],sum[]);
}
}
}
//printf("time=%.3lf",(double)clock()/CLOCKS_PER_SEC);
return ;
}
上一篇:NBUT 1602 Mod Three(线段树单点更新区间查询)


下一篇:Java带有运算符的字符串转换为Long型