莫隊 ---- 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
*/