莫队 ---- CF 135D. Jeff and Removing Periods （等差数列预处理 + 莫队）

题目

题目大意：

给你一个等差序列，每次查询一段区间 [ l , r ] [l,r] [l,r]的答案。 显然这是典型的不带修改的区间询问类问题，我们可以考虑用莫队算法去解决。

解题思路：

接下来看怎么递推 [ l , r ] [l,r] [l,r]到 [ l − 1 , r ] [l-1,r] [l−1,r]， [ l , r + 1 ] [l,r+1] [l,r+1]的关系

首先对区间的询问是： 每次 任选 a i a_i ai​, k k k，把 a i ai ai删掉，如 a i + k = = a i a_{i+k}==a_{i} ai+k​==ai​则一直删下去，也就是把值相等，且下标形成等差数列的一列数删掉， 余下的数重新排列。

问你删除完整个数列的最少操作数

显然，第一次删掉后重排的话，我们肯定可以把所有数排成公差为1的一个个等差数列。

• 所以其实 询问的意思就是： 如果第一次能找到一个数值，其所有出现的数的下标都形成等差数列（可以一次性删除），那么之后的操作步数实际就是 数值的种类数-1+1。

  因此 答案是 总种类数；

• 如果第一次找不到 一个数满足 所有出现的数的下标都形成等差数列 则答案就是 总的种类数+1
• 转移的话，需要预处理两个数组， fl[i]和fr[i]，fl[i]表示i位置往左找，第一个使得 a [ i ] a[i] a[i]不满足等差数列的位置，fr同理。

根据以下递推式：

inline void init() {
    for(int i = 1; i <= n; ++ i) {
        int p = arr[i];
        mp[p] = 1;
        pre[i] = last[p]; // 前驱
        last[p] = i;
        if(pre[i] - pre[pre[i]] == i - pre[i] || pre[pre[i]] == 0)
          fl[i] = fl[pre[i]];
        else fl[i] = pre[pre[i]];
    }
    for(auto it : mp) last[it.first] = n + 1;
    fr[n+1] = n+1;
    bak[0] = n+1;
    bak[n+1] = n+1;
    for(int i = n; i >= 1; -- i) {
        int p = arr[i];
        bak[i] = last[p]; // 后继
        last[p] = i;
        if(bak[bak[i]] - bak[i] == bak[i] - i || bak[bak[i]] == n + 1) 
          fr[i] = fr[bak[i]];
        else fr[i] = bak[bak[i]];
    }
}
           

预处理完后，

按照莫队算法，如果上一次区间为 [ l , r ] [l,r] [l,r]，那么下一次要add一个数的话，

如果 A d d Add Add的数第一次出现，则kind++, 且num_dengcha++

否则，看该数的加入是否会导致 num_dengcha减少。

即：if(fl[i]>=x&&fl[pre[i]]<x) dengcha–; 之前是等差，现在不是等差

如果是 S u b Sub Sub的话，

如果这个数只有一个，则显然kind–，num_dengcha–;

否则，看该数的减少会不会导致 num_dengcha的增加

即：if (fr[bak[i]]>R&&fr[i]<=R) dengcha++;

好了，接下来按照套路写莫队就好了

AC code

#include <bits/stdc++.h>
#define mid ((l + r) >> 1)
#define Lson rt << 1, l , mid
#define Rson rt << 1|1, mid + 1, r
#define ms(a,al) memset(a,al,sizeof(a))
#define log2(a) log(a)/log(2)
#define lowbit(x) ((-x) & x)
#define IOS std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define INF 0x3f3f3f3f
#define LLF 0x3f3f3f3f3f3f3f3f
#define f first
#define s second
#define endl '\n'
using namespace std;
const int N = 2e6 + 10, mod = 1e9 + 9;
const int maxn = 500010;
const long double eps = 1e-5;
const int EPS = 500 * 500;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
typedef pair<double,double> PDD;
template<typename T> void read(T &x) {
   x = 0;char ch = getchar();ll f = 1;
   while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
   while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
template<typename T, typename... Args> void read(T &first, Args& ... args) {
   read(first);
   read(args...);
}
int n, m, arr[maxn];
int fl[maxn], fr[maxn];
int pre[maxn], bak[maxn], last[maxn];
unordered_map<int,bool> mp;
inline void init() {
    for(int i = 1; i <= n; ++ i) {
        int p = arr[i];
        mp[p] = 1;
        pre[i] = last[p];
        last[p] = i;
        if(pre[i] - pre[pre[i]] == i - pre[i] || pre[pre[i]] == 0)
          fl[i] = fl[pre[i]];
        else fl[i] = pre[pre[i]];
    }
    for(auto it : mp) last[it.first] = n + 1;
    fr[n+1] = n+1;
    bak[0] = n+1;
    bak[n+1] = n+1;
    for(int i = n; i >= 1; -- i) {
        int p = arr[i];
        bak[i] = last[p];
        last[p] = i;
        if(bak[bak[i]] - bak[i] == bak[i] - i || bak[bak[i]] == n + 1) 
          fr[i] = fr[bak[i]];
        else fr[i] = bak[bak[i]];
    }
    // for(int i = 1; i <= n; ++ i)
    //   cout << fl[i] << " \n"[i == n];
    // for(int i = 1; i <= n; ++ i)
    //   cout << pre[i] << " \n"[i == n];
    // for(int i = 1; i <= n; ++ i) 
    //   cout << fr[i] << " \n"[i == n];
    // for(int i = 1; i <= n; ++ i)
    //   cout << bak[i] << " \n"[i == n];
}

struct node {
	int l, r, id;
	int b;
}q[maxn];

bool cmp1(node x,node y) {
    return x.b^y.b?x.b<y.b:x.b&1?x.r<y.r:x.r>y.r;
} 
int ans[maxn], res = 0, is;
int cnt[maxn];
inline void Add(int u, bool lorr, int i) {
	if(++ cnt[arr[u]] == 1) res ++, is ++;
    else {
        if(lorr) {// 这是判断是左右指针哪个在移动
            if(fr[bak[u]] > i && fr[u] <= i) is --; //之前是等差，现在不是等差, 
        } else {
            if(fl[pre[u]] < i && fl[u] >= i) is --;
        }
    }
}

inline void Sub(int u, bool lorr, int i) {
	if(-- cnt[arr[u]] == 0) res --, is --;
    else {
        if(lorr) {// 这是判断是左右指针哪个在移动
            if(fr[bak[u]] > i && fr[u] <= i) is ++;
        } else {
            if(fl[pre[u]] < i && fl[u] >= i) is ++;
        }
    }
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	int block = 500;
	for(int i = 1; i <= n; ++ i) cin >> arr[i];
    init();
    cin >> m;
	for(int i = 1; i <= m; ++ i) {
		int l, r;
		cin >> l >> r;
		q[i] = {l,r,i,(l-1)/block+1};
	}
    sort(q+1,q+1+m,cmp1);
	int l = 1, r = 0;
	for(int i = 1; i <= m; ++ i) {
		while(q[i].l < l) Add(--l,1,r);// 上个区间的r
		while(q[i].r > r) Add(++r,0,l);// 上个区间的l
		while(q[i].l > l) Sub(l++,1,r);
		while(q[i].r < r) Sub(r--,0,l);
		ans[q[i].id] = res - (is!=0) + 1;
	}
	for(int i = 1; i <= m; ++ i) 
	  cout << ans[i] << "\n";
	return 0;
}
/*
10
2 1 3 3 3 3 1 3 1 1
1
4 8
*/