string

string

【题目描述】

给定一个由小写字母组成的字符串s。有m次操作，每次操作给定3个参数l,r,x。如果x=1，将s[l] ~ s[r]升序排序；如果x=0，将s[l] ~ s[r]降序排序。你需要求出最终序列。

【输入数据】

第一行两个整数n,m。第二行一个字符串s。接下来m行每行三个整数x,l,r。

【输出数据】

一行一个字符串表示答案。

【样例输入】

5 2

cabcd

1 3

1

3 5

0

【样例输出】

abdcc

【数据范围】

对于40%的数据，n,m<=1000。

对于100%的数据，n,m<=100000

题解

这道题卡常卡得好严，打出正解也过不掉啊，我果然还是太菜了

就比暴力多二十分的代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath> 
#define N 100100
using namespace std; 

int n,m,tmp[27];
char s[N];

struct Segment_tree
{
	struct node
	{
		int l,r,sum,f;
	}T[N<<2];
	void pushup(int p){T[p].sum=T[p<<1].sum+T[p<<1|1].sum;}
	void build(int p,int x,int y,char v)
	{
		T[p].l=x;T[p].r=y;T[p].f=-1;
		if(x==y){if(s[x]==v)T[p].sum=1;return;}
		int mid=(x+y)>>1;
		build(p<<1,x,mid,v);
		build(p<<1|1,mid+1,y,v);
		pushup(p);
	}
	void pushdown(int p)
	{
		if(T[p].f==-1) return;
		T[p<<1].sum=(T[p<<1].r-T[p<<1].l+1)*T[p].f;
	    T[p<<1|1].sum=(T[p<<1|1].r-T[p<<1|1].l+1)*T[p].f;
	    T[p<<1].f=T[p<<1|1].f=T[p].f;
	    T[p].f=-1;
	}
	int query(int p,int x,int y)
	{
		int pl=T[p].l,pr=T[p].r;
		if(pl==x&&pr==y) return T[p].sum;
		pushdown(p);
		int mid=(pl+pr)>>1;
		if(y<=mid) return query(p<<1,x,y);
		else if(x>mid) return query(p<<1|1,x,y);
		return query(p<<1,x,mid)+query(p<<1|1,mid+1,y);
	}
	void set(int p,int x,int y,int v)
	{
		int pl=T[p].l,pr=T[p].r;
	    if(pl==x&&pr==y)
	    {
	        T[p].sum=(T[p].r-T[p].l+1)*v;
	        T[p].f=v;
	        return;
	    } 
	    pushdown(p);
	    int mid=(pl+pr)>>1;
	    if(y<=mid) set(p<<1,x,y,v);
	    else if(x>mid) set(p<<1|1,x,y,v);
	    else
	    {
	        set(p<<1,x,mid,v);
	        set(p<<1|1,mid+1,y,v);
	    }
	    pushup(p);
	}
	void get_ans(int p,int x,int y,char v)
	{
		if(x==y){if(T[p].sum)s[x]=v;return;}
		pushdown(p);
		int mid=(x+y)>>1;
		get_ans(p<<1,x,mid,v);
		get_ans(p<<1|1,mid+1,y,v);
		pushup(p);
	}
	
}st[27];

int main()
{
	scanf("%d%d%s",&n,&m,s+1);
	for(int i=0;i<26;i++) st[i].build(1,1,n,'a'+i);//对于每个字母，用一颗线段树维护 
	while(m--)
	{
		int l,r,opt;scanf("%d%d%d",&l,&r,&opt);
		for(int i=0;i<26;i++) tmp[i]=st[i].query(1,l,r);//先求出区间内字母i的个数
		for(int i=0;i<26;i++) st[i].set(1,l,r,0);//将区间清空 
		if(opt)//升序
		{
			int pos=l;
			for(int i=0;i<26;i++) if(tmp[i]) st[i].set(1,pos,pos+tmp[i]-1,1),pos+=tmp[i];
		}
		else//降序 
		{
			int pos=l;
			for(int i=25;i>=0;i--) if(tmp[i]) st[i].set(1,pos,pos+tmp[i]-1,1),pos+=tmp[i];
		}
	}
	for(int i=0;i<26;i++) st[i].get_ans(1,1,n,'a'+i);
	for(int i=1;i<=n;i++) printf("%c",s[i]);
	return 0;
}