URAL 1827 Indigenous Wars（排序、乱搞）

#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <queue>
using namespace std;

#define ll long long
#define MP make_pair

#define inf 0x3f3f3f3f
#define eps 1e-8

#define maxn 100010

int a[maxn];
struct node{
	int r,len;
	node(int _r,int _len):r(_r),len(_len){}
	bool operator < (const node& b) const{
		return len < b.len;
	}
};
vector<node>v[maxn];
int xx[maxn];
int main(){
	int n,m;
	while(~scanf("%d",&n)){
		for(int i=n-1;i>=0;--i) scanf("%d",a+i), xx[i] = a[i];
		sort(xx,xx+n);
		int nn = unique(xx,xx+n) - xx;
		for(int i=0;i<n;++i) a[i] = lower_bound(xx,xx+nn,a[i]) - xx;
		for(int i=0;i<=nn;++i) v[i].clear();
		scanf("%d",&m);
		for(int i=0;i<m;++i){
			int li,ri,leni;
			scanf("%d%d%d",&li,&ri,&leni);int lval=li,rval=ri;
			if(leni > n) continue;
			li = lower_bound(xx,xx+nn,li) - xx;
			ri = lower_bound(xx,xx+nn,ri) - xx;
			if(li==nn || ri==nn) continue;
			if(xx[li]!=lval || xx[ri]!=rval) continue;
			v[li].push_back(node(ri,leni));
		}
		for(int i=0;i<=nn;++i) sort(v[i].begin(),v[i].end());
		int add[maxn];
		memset(add,0,sizeof(add));
		for(int i=0;i<n;++i){
			for(int j=v[a[i]].size()-1;j>=0;--j){
				int len = v[a[i]][j].len;
				int val = v[a[i]][j].r;
				if(i+len-1 >= n) continue;
				if(a[i+len-1] == val){
					add[i]++;
					add[i+len]--;
					break;
				}
			}
		}
		for(int i=1;i<n;++i) add[i] += add[i-1];
		for(int i=n-1;i>=0;--i) printf("%c",add[i]>0?‘1‘:‘0‘);
		puts("");
	}
	return 0;
}