codeforces #351 D. Jeff and Removing Periods (线段树/树状数组判断位置成等差数列)

题目链接 题意：有n个数，每次可以删除掉数值相同并且所在位置成等差数列（只删2个数或者只删1个数应该也是可以的），删掉这些数以后可以将剩下的数重新以任意顺序排列，称为一次操作。现在给出m个询问，每个询问一个区间[l,r]，问删光区间[l,r]中的数最少需要的操作次数。

思路/题解：由于第一次操作之后可以重排，那么把相同的数放在一起得到一个位置的公差为1的等差数列，之后的答案显然是元素个数。所以需要判断初始的时候，是否能一次删光某个数值的数，也就是需要判断初始时刻是否有某个数出现的所有位置组成一个等差数列。

(去icpc-camp的论坛问了一波。。。链接在这里)

之前刚刚学了判断一个区间中不同的数有多少个的姿势。。。

所以问题就在于如何判断这个等差数列。。。

参考叉姐的思路，我的思路如下：

就是从左往右扫的时候，对于当前的数，看该种数在当前位置左边且离当前位置最近的不能和当前位置构成等差数列的数的位置，然后用树状数组判断这个位置和当前查询区间的左端点的关系，如果左端点在这个位置左边，就不是等差，否则就是等差。

上面是判断一种数的情况。。。我要找到一种数满足题意即可。。

具体做法：

从左到右扫描每个元素，对于每种数字，肯定是有最长的一段后缀是等差数列，假设是 xx 个，那么左端点落在第 x + 1x+1 个后，这种数字就是全是等差数列。 我们可以拿一个树状数组把从第 (x + 1)(x+1) 个数往后全部 +1，询问时只要询问某个元素是不是 >0 就可以了。

顺便说一句：叉姐人真的好nice啊。。本来昨天大概找了大半天题解。。看了代码也没看懂。。。

然后晚上去icpc-camp的论坛上问了一波。。。

然后茶姐的回复窝仍然看不懂。。。。。

感觉窝问的应该不是什么困难的问题（虽然我想了好久都想不出）。。。

所以纠结了好久要不要再问一下叉姐。。。。

最后还是问了。。。结果叉姐非常热心而又详细地回答了我。。。。

真是让我这种蒟蒻感动不已啊。。。。orz

怪不得人人爱叉姐。

/* ***********************************************
Author :111qqz
Created Time :Sun 18 Sep 2016 08:30:02 PM CST
File Name :code/cf/problem/351D.cpp
************************************************ */
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair
using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int N=1E5+7;
int a[N],pre[N],lst[N];
int n,m;
int tree[N<<2];
int t[N];
int ans[N];
struct node
{
    int l,r;
    int id;
    bool operator < (node b)const
    {
	if (r==b.r) return l<b.l;
	return r<b.r;
    }
}q[N];
void PushUp(int rt){tree[rt] = tree[rt<<1] + tree[rt<<1|1];}
void update( int p,int sc,int l,int r,int rt)
{
    if (l==r)
    {
	tree[rt]+=sc;
	return ;
    }
    int m = (l+r)>>1;
    if (p<=m) update(p,sc,lson);
    else update(p,sc,rson);
    PushUp(rt);
}
int query(int L,int R,int l,int r,int rt)
{
    if (L<=l&&r<=R) return tree[rt];
    int m = (l+r)>>1;
    int ret = 0;
    if (L<=m) ret += query(L,R,lson);
    if (R>=m+1) ret +=query(L,R,rson);
    return ret;
}
int lowbit( int x)
{
    return x&(-x);
}
void update2( int x,int delta)
{
    for ( int i = x; i < N ; i+=lowbit(i)) t[i]+=delta;
}
int Sum( int x)
{
    int res = 0 ;
    for ( int i = x; i >=1 ; i-=lowbit(i)) res+=t[i];
    return res;
}
int main()
{
	#ifndef  ONLINE_JUDGE 
	freopen("code/in.txt","r",stdin);
  #endif
	cin>>n;
	ms(tree,0);
	ms(t,0);
	for ( int i = 1; i  <= n ; i++)
	{
	    //cin>>a[i];
	    scanf("%d",a+i);
	    pre[i] = lst[a[i]];//pre[i]表示a[i]上次出现的位置。
	    lst[a[i]] =  i;
	}
	cin>>m;
	for ( int i = 1; i <= m ; i++)
	{
	    scanf("%d %d",&q[i].l,&q[i].r);
	    //cin>>q[i].l>>q[i].r;
	    q[i].id = i ;
	}
	sort(q+1,q+m+1);
	int cur = 1;
	for ( int i = 1 ; i <= m ; i ++)
	{
	    for ( ; cur <= q[i].r ; cur++)
	    {
		if (pre[cur]) update(pre[cur],-1,1,n,1);
		update(cur,1,1,n,1);
		update2(pre[cur]+1,1);
		update2(cur+1,-1); //+1是bit的下标问题。。从0开始会死循环。。。
		if (pre[cur])
		{
		    int k = pre[cur];
		    if (!pre[k]||k-pre[k]==cur-k);
		    else
		    {
			int len = k - pre[k];
			k = pre[k];
			for ( ;k;)
			{
			    int A = pre[k];
			    update2(A+1,-1); //中间位置会被抵消。。。只会留下距离当前位置最近的不满足等差的条件的数（可能是不存在，就是0+1==1,或者长度不相等）
			    update2(k+1,1);
			    if (!A||k-A!=len) break;
			    k = A;
			}
		    }
		}
	    }
	    ans[q[i].id] = query(q[i].l,q[i].r,1,n,1) + (Sum(q[i].l)==0);
	}
	for ( int i = 1; i  <= m ; i++) cout<<ans[i]<<endl;
  #ifndef ONLINE_JUDGE  
  fclose(stdin);
  #endif
    return 0;
}