小A的题（线段树）
发布时间
阅读量：
阅读量
描述
由于小 A 实在是太菜了，因此他现在需要你的帮助： 现在小 A 手上有一个凌乱的 01 串，他想通过若干次对于这个 01 串的局部排序将它变成一个有趣的 01 序列。 现在有两种操作：
输入格式
l r 0 表示把区间 [l,r][l,r] 给升序排序
l rr1 表示把区间 [l,r][l,r] 给降序排序
然后小 A 这个菜鸡想知道在 m 次操作之后序列长啥样。
输出格式
第一行一个 0101 串 S。 第二行一个整数 m。 接下来 m 行每行三个整数 l,r,x, x=0，1中的一个。
m 次操作之后的 01 串
数据范围
∣S∣≤1000000,m≤500000
输出时每行末尾的多余空格，不影响答案正确性
样例输入
样例输出
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <string>
#include <cstdio>
#define mem(a) memset(a,0,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn=1000100;
int a[maxn];
int sum[maxn*4];
int Add[maxn*4];
char str[maxn];
int n,m,x,y,z,q,len;
void PushUp(int n)
{
sum[n]=sum[n*2]+sum[n*2+1];
return;
}
void Build(int l,int r,int num)
{
if(l==r)
{
sum[num]=a[l];
return;
}
int m=(l+r)/2;
Build(l,m,num*2);
Build(m+1,r,num*2+1);
PushUp(num);
return;
}
void PushDown(int num,int ln,int rn)
{
if(Add[num]==1)
{
Add[num*2]=1;
Add[num*2+1]=1;
sum[num*2]=ln;
sum[num*2+1]=rn;
Add[num]=0;
}
else if(Add[num]==-1)
{
Add[num*2]=-1;
Add[num*2+1]=-1;
sum[num*2]=0;
sum[num*2+1]=0;
Add[num]=0;
}
return;
}
void Update(int L,int R,int C,int l,int r,int num)
{
if(l>=L&&R>=r)
{
if(C==0)
{
if(Add[num]!=0)
{
int m=(l+r)/2;
PushDown(num,m-l+1,r-m);
}
sum[num]=0;
Add[num]=-1;
return;
}
if(Add[num]!=0)
{
int m=(l+r)/2;
PushDown(num,m-l+1,r-m);
}
sum[num]=r-l+1;
Add[num]=1;
return;
}
int m=(l+r)/2;
PushDown(num,m-l+1,r-m);
if(L<=m)
Update(L,R,C,l,m,num*2);
if(R>=m+1)
Update(L,R,C,m+1,r,num*2+1);
PushUp(num);
return;
}
int Query(int L,int R,int l,int r,int num)
{
if(L<=l&&R>=r)
{
return sum[num];
}
int m=(l+r)/2;
PushDown(num,m-l+1,r-m);
int ans=0;
if(L<=m)
ans+=Query(L,R,l,m,num*2);
if(R>=m+1)
ans+=Query(L,R,m+1,r,num*2+1);
return ans;
}
void print(int l,int r,int num)
{
if(l==r)
{
if(sum[num]==1)
printf("1");
else
printf("0");
return;
}
if(sum[num]==r-l+1)
{
for(int i=l;i<=r;i++)
printf("1");
return;
}
if(sum[num]==0)
{
for(int i=l;i<=r;i++)
printf("0");
return;
}
int m=(l+r)/2;
PushDown(num,m-l+1,r-m);
print(l,m,num*2);
print(m+1,r,num*2+1);
}
int main()
{
memset(Add,0,sizeof(Add));
scanf("%s",str+1);
len=strlen(str+1);
for(int i=1; i<=len; i++)
{
if(str[i]=='1')
a[i]=1;
else
a[i]=0;
}
Build(1,len,1);
scanf("%d",&q);
while(q--)
{
scanf("%d %d %d",&x,&y,&z);
int s=Query(x,y,1,len,1);
if(s==0)
continue;
if(s==y-x+1)
continue;
Update(x,y,0,1,len,1);
if(z==0)
Update(y-s+1,y,1,1,len,1);
else
Update(x,x+s-1,1,1,len,1);
}
print(1,len,1);
return 0;
}
AI写代码全部评论 (0)
还没有任何评论哟~