http://codeforces.com/problemset/problem/351/D
题意：
n个数的一个序列，m个操作
给出操作区间[l,r]，
首先可以删除下标为等差数列且数值相等的一些数
然后可以对区间剩余数重排
继续删除下标为等差数列且数值相等的一些数
继续对区间进行重排
直至区间内没有数
问每次操作的最少删除次数
因为每次删除后可以重排
那么完全可以在第一次删除后就把区间相等的数排在一起
这样相等的数的下标就分别构成了公差为1的等差数列
所以问题转化为
设区间[l,r]内数有x种，
若在区间内有一种数，他的位置下标构成等差数列，输出x
否则，输出x+1
本题可以离线操作
区间内数的种类，用莫队算法很容易做
所以问题只剩下如何用莫队算法维护区间内 相同的数的下标构成等差序列 的数的种数
思路：
加一个数：
如果这个数在区间里没有出现过，等差序列数+1
否则，若加的数破坏了原有的一个等差序列，等差序列数-1
删一个数：
如果这个数在区间里只剩下1个，等差序列数-1
否则，若删的数使原来不能构成 等差序列的数构成了等差序列，等差序列数+1
每次操作的答案=区间数的种数+ k
若等差序列数=0，则k=1，否则k=0
具体实现：
预处理fl[i],fr[i]表示第i个数左/右第一个 相等但下标不能构成等差序列的位置
为了得到这个，还需要两个数组：
pre[i] i左边第一个和i相等的数的位置
bac[i] i右边第一个和i相等的数的位置
若pre[pre[i]]-pre[i]==i-pre[i] 或者 pre[i]==0 fl[i]=fl[pre[i]]（两个数一定是等差数列）
否则 fl[i]=pre[pre[i]]
fr同理
设莫队维护的当前区间为[L,R]
破坏等差数列：
若此时L正在递减，那就是fr[bac[i]]>R && fr[i]<=R
若此时R正在递增，那就是fl[pre[i]]<L && fl[i]>=L
产生等差数列：
若此时L正在递增，那就是fr[i]<=R && fr[bac[i]]>R
若此时R正在递减，那就是fl[i]>=L && fl[pre[i]]<L
#include<cmath>
#include<cstdio>
#include<iostream>
#include<algorithm> using namespace std; #define N 100002 int val[N],last[N];
int pre[N],fl[N];
int bac[N],fr[N]; struct node
{
int l,r;
int id;
}e[N]; int bl[N]; int sum[N]; int ans[N]; void read(int &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
} bool cmp(node p,node q)
{
if(bl[p.l]!=bl[q.l]) return bl[p.l]<bl[q.l];
return p.r<q.r;
} int main()
{
int n;
read(n);
int x,y;
for(int i=;i<=n;++i)
{
read(val[i]);
pre[i]=last[val[i]];
last[val[i]]=i;
if(pre[pre[i]]-pre[i]==pre[i]-i || !pre[i]) fl[i]=fl[pre[i]];
else fl[i]=pre[pre[i]];
}
for(int i=;i<=n;++i) last[i]=n+;
fr[n+]=n+;
for(int i=n;i;--i)
{
bac[i]=last[val[i]];
last[val[i]]=i;
if(bac[bac[i]]-bac[i]==bac[i]-i || bac[i]==n+) fr[i]=fr[bac[i]];
else fr[i]=bac[bac[i]];
}
int m;
read(m);
for(int i=;i<=m;++i)
{
read(e[i].l);
read(e[i].r);
e[i].id=i;
}
int siz=sqrt(n);
for(int i=;i<=n;++i) bl[i]=(i-)/siz+;
sort(e+,e+m+,cmp);
int L=,R=,tmp=,dengcha=;
for(int j=;j<=m;++j)
{
x=e[j].l; y=e[j].r; for(int i=L-;i>=x;--i)
{
if(!sum[val[i]])
{
dengcha++;
tmp++;
}
else
{
if(fr[i]<=R && fr[bac[i]]>R) dengcha--;
}
sum[val[i]]++;
}
for(int i=L;i<x;++i)
{
if(sum[val[i]]==)
{
dengcha--;
tmp--;
}
else
{
if(fr[i]<=R && fr[bac[i]]>R) dengcha++;
}
sum[val[i]]--;
}
for(int i=R;i>y;--i)
{
if(sum[val[i]]==)
{
dengcha--;
tmp--;
}
else
{
if(fl[i]>=x && fl[pre[i]]<x) dengcha++;
}
sum[val[i]]--;
}
for(int i=R+;i<=y;++i)
{
if(!sum[val[i]])
{
dengcha++;
tmp++;
}
else
{
if(fl[i]>=x && fl[pre[i]]<x) dengcha--;
}
sum[val[i]]++;
}
L=x; R=y;
ans[e[j].id]=tmp+;
if(dengcha>) ans[e[j].id]--;
}
for(int i=;i<=m;++i) cout<<ans[i]<<'\n';
}
3 seconds
256 megabytes
standard input
standard output
Cosider a sequence, consisting of n integers: a1, a2, ..., an. Jeff can perform the following operation on sequence a:
- take three integers v, t, k (1 ≤ v, t ≤ n; 0 ≤ k; v + tk ≤ n), such that av = av + t, av + t = av + 2t, ..., av + t(k - 1) = av + tk;
- remove elements av, av + t, ..., av + t·k from the sequence a, the remaining elements should be reindexed a1, a2, ..., an - k - 1.
- permute in some order the remaining elements of sequence a.
A beauty of a sequence a is the minimum number of operations that is needed to delete all elements from sequence a.
Jeff's written down a sequence of m integers b1, b2, ..., bm. Now he wants to ask q questions. Each question can be described with two integers li, ri. The answer to the question is the beauty of sequence bli, bli + 1, ..., bri. You are given the sequence b and all questions. Help Jeff, answer all his questions.
The first line contains integer m (1 ≤ m ≤ 105). The next line contains m integers b1, b2, ..., bm (1 ≤ bi ≤ 105).
The third line contains integer q (1 ≤ q ≤ 105) — the number of questions. The next q lines contain pairs of integers, i-th of them contains a pair of integers li, ri (1 ≤ li ≤ ri ≤ m) — the description of i-th question.
In q lines print the answers to Jeff's queries. Print the answers according to the order of questions in input.
5
2 2 1 1 2
5
1 5
1 1
2 2
1 3
2 3
2
1
1
2
2
10
2 1 3 3 3 3 1 3 1 1
10
4 8
2 10
1 10
4 4
1 3
2 4
6 7
1 9
2 5
1 1
2
3
3
1
3
2
2
3
2
1