http://acm.hdu.edu.cn/showproblem.php?pid=6483
Problem Description
One day, WNJXYK found a very hard problem on an Online Judge. This problem is so hard that he had been thinking about the solutions for a couple of days. And then he had a surprise that he misunderstood that problem and easily figured out a solution using segment tree. Now he still wonders that solution for the misread problem.
There is a sequence with N positive integers A1,A2,…,An and M queries. Each query will give you an interval [L,R] and require an answer with YES/NO indicates that whether the numbers in this interval are continuous in its integer range.
Let us assume that the maximal number in an interval is mx and the minimal number is mi. The numbers in this interval are continuous in its integer range means that each number from mi to mx appears at least once in this interval.
题意：给定长为n的序列 (规模106)，要求回答m次询问，每次询问是：[L,R]区间包含的元素是不是连续的，所谓连续，指[L,R]区间的最大值与最小值之间的所有值都在这个区间内出现过。
思路：
方法1：莫队的裸操作就是：维护区间不同元素的个数，这个题目转化为对原序列RMQ求取区间max和min，然后离散化（因为元素是1e9级别的），如果连续的话，这个区间不同值个数=max-min+1。
注意不能离散化后求RMQ，否则124就变成123连续了。
#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) (x&(-x))
#define maxn (100000+100)
int SIZE,T,n,m,a[maxn];
vector<int> nums;
int stMax[20][maxn],stMin[20][maxn];
bool ans[maxn];
int cnt[maxn],now_ans;
struct Query{
int id,l,r;
bool operator < (Query x)const{
if(l/SIZE!=x.l/SIZE)return l/SIZE<x.l/SIZE;
return r<x.r;
}
}Q[maxn];
void RMQ_init()
{
for(int i=1;i<=n;i++)stMax[0][i]=stMin[0][i]=a[i];
for(int k=1;(1<<k)<=n;k++)
{
for(int i=1;i+(1<<k)-1<=n;i++)
{
stMax[k][i]=max(stMax[k-1][i],stMax[k-1][i+(1<<(k-1))]);
stMin[k][i]=min(stMin[k-1][i],stMin[k-1][i+(1<<(k-1))]);
}
}
}
int query(int l,int r)
{
int k=0;
while((1<<(k+1))<=r-l+1)k++;
return max(stMax[k][l],stMax[k][r-(1<<k)+1])-min(stMin[k][l],stMin[k][r-(1<<k)+1])+1;
}
void init()
{
cin>>n>>m;
SIZE=sqrt(n);
nums.clear();
for(int i=1;i<=n;i++)scanf("%d",&a[i]),nums.push_back(a[i]);
RMQ_init();
for(int i=1;i<=m;i++)scanf("%d%d",&Q[i].l,&Q[i].r),Q[i].id=i;
sort(Q+1,Q+1+m);
sort(nums.begin(),nums.end());
int num=unique(nums.begin(),nums.end())-nums.begin();
nums.resize(num);
for(int i=1;i<=n;i++)a[i]=lower_bound(nums.begin(),nums.end(),a[i])-nums.begin()+1;
}
void move(int p,int flag)
{
if(flag==1){
cnt[a[p]]++;
if(cnt[a[p]]==1)now_ans++;
}else{
cnt[a[p]]--;
if(cnt[a[p]]==0)now_ans--;
}
}
void solve()
{
memset(cnt,0,sizeof(cnt));
now_ans=0;
int l=Q[1].l,r=l-1;
for(int i=1;i<=m;i++)
{
while(l>Q[i].l)move(--l,1);
while(r<Q[i].r)move(++r,1);
while(l<Q[i].l)move(l++,-1);
while(r>Q[i].r)move(r--,-1);
ans[Q[i].id] = (query(l,r)==now_ans);
}
for(int i=1;i<=m;i++)printf("%s\n",ans[i]?"YES":"NO");
}
int main()
{
//freopen("input.in","r",stdin);
cin>>T;
while(T--)
{
init();
solve();
}
return 0;
}
方法2：按询问的区间右端点排序，用树状数组做。这个方法的思想是：对于若干个右端点为R的区间，比如 [l1,r],[l2,r],[l3,r]这些，对于每个元素，只需要维护它在[1,R]最后一次出现的位置即可，然后区间不同值的个数就是 sum(R)−sum(l−1)
#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) (x&(-x))
#define maxn (100000+100)
int T,n,m,a[maxn];
vector<int> nums;
int stMax[20][maxn],stMin[20][maxn];
bool ans[maxn];
int c[maxn],pos[maxn];
struct Query{
int id,l,r;
bool operator < (Query x)const{
return r<x.r;
}
}Q[maxn];
void add(int p,int d)
{
while(p<=n)
{
c[p]+=d;
p+=lowbit(p);
}
}
int sum(int p)
{
int ret=0;
while(p)
{
ret+=c[p];
p-=lowbit(p);
}
return ret;
}
void RMQ_init()
{
for(int i=1;i<=n;i++)stMax[0][i]=stMin[0][i]=a[i];
for(int k=1;(1<<k)<=n;k++)
{
for(int i=1;i+(1<<k)-1<=n;i++)
{
stMax[k][i]=max(stMax[k-1][i],stMax[k-1][i+(1<<(k-1))]);
stMin[k][i]=min(stMin[k-1][i],stMin[k-1][i+(1<<(k-1))]);
}
}
}
int query(int l,int r)
{
int k=0;
while((1<<(k+1))<=r-l+1)k++;
return max(stMax[k][l],stMax[k][r-(1<<k)+1])-min(stMin[k][l],stMin[k][r-(1<<k)+1])+1;
}
void init()
{
cin>>n>>m;
nums.clear();
for(int i=1;i<=n;i++)scanf("%d",&a[i]),nums.push_back(a[i]);
RMQ_init();
for(int i=1;i<=m;i++)scanf("%d%d",&Q[i].l,&Q[i].r),Q[i].id=i;
sort(Q+1,Q+1+m);
sort(nums.begin(),nums.end());
int num=unique(nums.begin(),nums.end())-nums.begin();
nums.resize(num);
for(int i=1;i<=n;i++)a[i]=lower_bound(nums.begin(),nums.end(),a[i])-nums.begin()+1;
}
void solve()
{
memset(c,0,sizeof(c));
memset(pos,0,sizeof(pos));
for(int i=1,j=1;i<=n&&j<=m;i++)
{
if(pos[a[i]])add(pos[a[i]],-1);
pos[a[i]]=i;add(i,1);
while(Q[j].r==i)
{
ans[Q[j].id]=(query(Q[j].l,Q[j].r)==sum(Q[j].r)-sum(Q[j].l-1));
j++;
}
}
for(int i=1;i<=m;i++)printf("%s\n",ans[i]?"YES":"NO");
}
int main()
{
//freopen("input.in","r",stdin);
cin>>T;
while(T--)
{
init();
solve();
}
return 0;
}
京公网安备 11010502036488号