[TIOJ] 1952. 小向的試煉 3-3：鑰匙(Key)/[Codeforces] 558E A Simple Task

題目連結:http://tioj.infor.org/problems/1952或http://codeforces.com/problemset/problem/558/E

---

本題要每次都對某個區間按小到大或大到小排序，那字串排序大概會想到counting sort，不難發現counting sort就是在對那個區間的a-z各自求和，之後再按順序填回去。這時就會有似曾相似的感覺了吧......吧，那就是區間求和跟區間修改，顯然用線段樹可以做到，不過要開a-z共26顆線段樹，每次要修改前就區間查和然後先歸零再把前面都改成一，最後輸出的時候就每個字元都查詢一下是哪一個，大概就這樣吧
p.s 第一次寫區間修改區間查詢的線段樹，怎麼運用懶標記卡了有點久ww
再p.s 其實這題有更快的作法，詳細解法可以看看余柏敘大大的code

#include <bits/stdc++.h>
using namespace std;
#define unset -1
#define N 100000

struct segNode{
	int l,r,val;
	int m;
};

void buildTree(int,int,int,int);
segNode segTree[26][N*4];
void modify(int, int, int, int, int);
int query(int, int, int, int);
void push(int,int);
int gVal(int,int);

int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	char str[N+5];
	scanf("%s",str);
	for(int i=0;i<26;i++){
		buildTree(i,0,n,0);
	}
	for(int i=0;i<n;i++){
		modify(str[i]-'a', i,i+1,1 , 0);
	}
	for(int i=0;i<m;i++){
		int l,r,type;
		scanf("%d%d%d",&l,&r,&type);
		l--;
		if(type==1){
			//a<b
			int kk=0;
			for(int j=0;j<26;j++){
				int sum = query(j,l,r,0);
				if(sum==0)continue;
				modify(j,l,r,0,0);
				modify(j,l+kk,l+kk+sum,1,0);
				kk+=sum;
			}
		}else{
			//b>a
			int kk=0;
			for(int j=0;j<26;j++){
				int sum = query(j,l,r,0);
				if(sum==0)continue;
				modify(j,l,r,0,0);
				modify(j,r-kk-sum,r-kk,1,0);
				kk+=sum;
			}
		}
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<26;j++){
			int k = query(j,i,i+1,0);
			if(k==1){
				putchar('a'+j);
				break;
			}
		}
	}
	return 0;
}

void buildTree(int w,int l,int r,int id){
	segTree[w][id].l=l;
	segTree[w][id].r=r;
	segTree[w][id].val=0;
	segTree[w][id].m=unset;
	if(l+1!=r){
		int mid = (l+r)/2;
		buildTree(w,l,mid,id*2+1);
		buildTree(w,mid,r,id*2+2);
	}
}

void modify(int w, int l, int r,int val, int id){
	if(segTree[w][id].m!=unset)
		push(w,id);
	if(l == segTree[w][id].l && r == segTree[w][id].r){
		segTree[w][id].m=val;
	}else{
		int segMid = (segTree[w][id].l+segTree[w][id].r)/2;
		if(r<=segMid){
			modify(w,l,r,val,id*2+1);
		}else if(l>=segMid){
			modify(w,l,r,val,id*2+2);
		}else{
			modify(w,l,segMid,val,id*2+1);
			modify(w,segMid,r,val,id*2+2);
		}
		segTree[w][id].val = gVal(w,id*2+1)+gVal(w,id*2+2);
	}
}

int query(int w,int l, int r,int id){
	if(segTree[w][id].m!=unset)
		push(w,id);
	if(l == segTree[w][id].l && r == segTree[w][id].r){
		return segTree[w][id].val;
	}else{
		int segMid = (segTree[w][id].l+segTree[w][id].r)/2;
		if(r<=segMid){
			return query(w,l,r,id*2+1);
		}else if(l>=segMid){
			return query(w,l,r,id*2+2);
		}else{
			int ll = query(w,l,segMid,id*2+1);
			int rr = query(w,segMid,r,id*2+2);
			return ll+rr;
		}
	}
}

void push(int w,int id){
	segTree[w][id].val = segTree[w][id].m*(segTree[w][id].r-segTree[w][id].l);
	if(segTree[w][id].l+1!=segTree[w][id].r){
		segTree[w][id*2+1].m=segTree[w][id].m;
		segTree[w][id*2+2].m=segTree[w][id].m;
	}
	segTree[w][id].m = unset;
}

int gVal(int w, int id){
	if(segTree[w][id].m==unset){
		return segTree[w][id].val;
	}else{
		return segTree[w][id].m*(segTree[w][id].r-segTree[w][id].l);
	}
}