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
怪不得人人爱叉姐。
1/* ***********************************************
2Author :111qqz
3Created Time :Sun 18 Sep 2016 08:30:02 PM CST
4File Name :code/cf/problem/351D.cpp
5************************************************ */
6#include <cstdio>
7#include <cstring>
8#include <iostream>
9#include <algorithm>
10#include <vector>
11#include <queue>
12#include <set>
13#include <map>
14#include <string>
15#include <cmath>
16#include <cstdlib>
17#include <ctime>
18#define fst first
19#define sec second
20#define lson l,m,rt<<1
21#define rson m+1,r,rt<<1|1
22#define ms(a,x) memset(a,x,sizeof(a))
23typedef long long LL;
24#define pi pair < int ,int >
25#define MP make_pair
26using namespace std;
27const double eps = 1E-8;
28const int dx4[4]={1,0,0,-1};
29const int dy4[4]={0,-1,1,0};
30const int inf = 0x3f3f3f3f;
31const int N=1E5+7;
32int a[N],pre[N],lst[N];
33int n,m;
34int tree[N<<2];
35int t[N];
36int ans[N];
37struct node
38{
39 int l,r;
40 int id;
41 bool operator < (node b)const
42 {
43 if (r==b.r) return l<b.l;
44 return r<b.r;
45 }
46}q[N];
47void PushUp(int rt){tree[rt] = tree[rt<<1] + tree[rt<<1|1];}
48void update( int p,int sc,int l,int r,int rt)
49{
50 if (l==r)
51 {
52 tree[rt]+=sc;
53 return ;
54 }
55 int m = (l+r)>>1;
56 if (p<=m) update(p,sc,lson);
57 else update(p,sc,rson);
58 PushUp(rt);
59}
60int query(int L,int R,int l,int r,int rt)
61{
62 if (L<=l&&r<=R) return tree[rt];
63 int m = (l+r)>>1;
64 int ret = 0;
65 if (L<=m) ret += query(L,R,lson);
66 if (R>=m+1) ret +=query(L,R,rson);
67 return ret;
68}
69int lowbit( int x)
70{
71 return x&(-x);
72}
73void update2( int x,int delta)
74{
75 for ( int i = x; i < N ; i+=lowbit(i)) t[i]+=delta;
76}
77int Sum( int x)
78{
79 int res = 0 ;
80 for ( int i = x; i >=1 ; i-=lowbit(i)) res+=t[i];
81 return res;
82}
83int main()
84{
85 #ifndef ONLINE_JUDGE
86 freopen("code/in.txt","r",stdin);
87 #endif
88 cin>>n;
89 ms(tree,0);
90 ms(t,0);
91 for ( int i = 1; i <= n ; i++)
92 {
93 //cin>>a[i];
94 scanf("%d",a+i);
95 pre[i] = lst[a[i]];//pre[i]表示a[i]上次出现的位置。
96 lst[a[i]] = i;
97 }
98 cin>>m;
99 for ( int i = 1; i <= m ; i++)
100 {
101 scanf("%d %d",&q[i].l,&q[i].r);
102 //cin>>q[i].l>>q[i].r;
103 q[i].id = i ;
104 }
105 sort(q+1,q+m+1);
106 int cur = 1;
107 for ( int i = 1 ; i <= m ; i ++)
108 {
109 for ( ; cur <= q[i].r ; cur++)
110 {
111 if (pre[cur]) update(pre[cur],-1,1,n,1);
112 update(cur,1,1,n,1);
113 update2(pre[cur]+1,1);
114 update2(cur+1,-1); //+1是bit的下标问题。。从0开始会死循环。。。
115 if (pre[cur])
116 {
117 int k = pre[cur];
118 if (!pre[k]||k-pre[k]==cur-k);
119 else
120 {
121 int len = k - pre[k];
122 k = pre[k];
123 for ( ;k;)
124 {
125 int A = pre[k];
126 update2(A+1,-1); //中间位置会被抵消。。。只会留下距离当前位置最近的不满足等差的条件的数（可能是不存在，就是0+1==1,或者长度不相等）
127 update2(k+1,1);
128 if (!A||k-A!=len) break;
129 k = A;
130 }
131 }
132 }
133 }
134 ans[q[i].id] = query(q[i].l,q[i].r,1,n,1) + (Sum(q[i].l)==0);
135 }
136 for ( int i = 1; i <= m ; i++) cout<<ans[i]<<endl;
137 #ifndef ONLINE_JUDGE
138 fclose(stdin);
139 #endif
140 return 0;
141}