hdu5172 – GTY’s gay friends(线段树)

题目链接 hdu5172

【题意】GTY有n个基友，出于某种恶趣味，GTY每天早上会让他的基友们排成一行，每个基友有一个特征值，表示基友有多雄壮或娘炮，你，作为GTY的助手，必须回答GTY的每个询问，GTY每次会问一个区间[l,r] 是否为一个1到r−l+1的排列。

【分析】这场BC是打得烂爆了，第一题忘记log的存在了然后就爆0了；回到这题，这题我现在只会线段树的做法，首先如果区间[l,r]要是一个1~r-l+1的排列的话就需要满足两个条件：

一：[l,r]的和为(1+r-l+1)*(1+r-l+1)/2;

二：使得[l,r]中每个数互相不重复；

第一个简单，前缀和搞定，对于第二个条件，用p[i]记录当前位置的数字在前一个最近的位置(需要加个w[j]记录每个数字j的最后一个位置)，然后线段树求出每个区间[l,r]的最大的p[]就可以了，只要p<l(区间左下标)就说明区间[l,r]里面没有重复的数字。

【AC CODE】1419ms

#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <map>
//#include <unordered_map>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
#define id(x,y) (x+y|x!=y)
const int INF = 0x3f3f3f3f, MAXN = 1000000+10;
int w[MAXN],p[MAXN], mx[MAXN<<1];
LL sum[MAXN];

inline void push_up(int x, int y, int m)
{
	mx[id(x,y)] = max(mx[id(x,m)],mx[id(m+1,y)]);
}
void bulid(int x, int y)
{
	if(x == y)
	{
		mx[id(x,y)] = p[x];
		return;
	}
	int m = (x+y)>>1;
	bulid(x,m);
	bulid(m+1,y);
	push_up(x,y,m);
}
int ql,qr;
int query(int x, int y)
{
	if(ql <= x && y <= qr)
		return mx[id(x,y)];
	int m = (x+y)>>1;
	int ans = -1;
	if(ql <= m) ans = max(ans,query(x,m));
	if(qr > m) ans = max(ans,query(m+1,y));
	return ans;
}
int main()
{
#ifdef SHY
	freopen("e:\\1.txt", "r", stdin);
#endif
	int n,m;
	sum[0] = 0;
	while(~scanf("%d %d%*c", &n, &m))
	{
		clc(w,-1);
		int a;
		repe(i,1,n)
		{
			scanf("%d%*c", &a);
			sum[i] = sum[i-1]+a;
			p[i] = w[a];
			w[a] = i;
		}
		bulid(1,n);
		rep(i,0,m)
		{
			scanf("%d %d%*c", &ql, &qr);
			LL num = qr-ql+1;
			if(sum[qr]-sum[ql-1] == (1+num)*num/2 && query(1,n) < ql) puts("YES");
			else puts("NO");
		}
	}
	return 0;
}