参考文献。
CF407E k-d-sequence
首先特判掉 \(d = 0\) 的情况。
发现模 \(d\) 余数不同的两个数 \(a, b\) 不可能形成一个等差数列，于是我们可以以余数将原序列分割为若干个连续段。然后我们对于每个右端点求出最远的左端点，发现限制是 \(maxn - minn + 1 \le len + k\)，其中 \(maxn = \max \lfloor \frac {a_i} d \rfloor, minn = \min \lfloor \frac {a_i} d \rfloor\)。整理一下限制得 \(maxn - minn - len \le k-1\)。于是我们使用单调栈维护 maxn 和 minn，然后使用线段树维护 \(maxn - minn - len\) 即可。
然后你发现你样例都过不去。你发现你没考虑两个数相同的情况，特判一下就过了。
#include <bits/stdc++.h>
#include <bits/extc++.h>
#define llong long long
#define N 200005
using namespace std;
using namespace __gnu_pbds;namespace IO{#define bs (1<<20)char buf1[bs], buf2[bs], *p1 = buf1, *p2 = buf1, *p3 = buf2;#define gc() (p1==p2&&(p2=(p1=buf1)+fread(buf1,1,bs,stdin),p1==p2)?EOF:*p1++)#define pc(x) (p3==buf2+bs?(fwrite(buf2,1,bs,stdout),*(p3=buf2)++=x):*p3++=x)struct F{~F(){fwrite(buf2,1,p3-buf2,stdout);}} f;template<typename T>inline void read(T& x){x = 0; int w = 1;char ch = gc();while(ch < '0' || ch > '9'){if(ch == '-') w = -w;ch = gc();}while(ch >= '0' && ch <= '9')x = (x<<3)+(x<<1)+(ch^48), ch = gc();x *= w;}template<typename T, typename... Args>inline void read(T& x, Args&... y){return read(x), read(y...);}template<typename T>inline void write(T x){if(x == 0) return pc(48), void();int s[32], top = 0;while(x) s[++top] = x%10, x /= 10;while(top) pc(s[top--]^48);}inline void write(char x){return pc(x), void();}template<typename T, typename... Args>inline void write(T x, Args... y){return write(x), write(y...);}}using IO::read;
using IO::write;int n, k, d;
int a[N], b[N];
int ans, ansl;
gp_hash_table<int, int> vis;#define mod(x) ((x%d+d)%d)
#define div(x) ((x-mod(x))/d)llong val[N<<2], tag1[N<<2], tag2[N<<2];
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
#define mid ((l+r)>>1)inline void addtag1(int x){val[x] = 0, tag2[x] = 0;tag1[x] = true;return;
}
inline void addtag2(int x, int k){val[x] += k, tag2[x] += k;return;
}
inline void pushdown(int x){if(tag1[x]){addtag1(ls(x)), addtag1(rs(x));tag1[x] = false;}if(tag2[x]){addtag2(ls(x), tag2[x]);addtag2(rs(x), tag2[x]);tag2[x] = 0;}return;
}
inline void add(int L, int R, int k, int x = 1, int l = 1, int r = n){if(L <= l && R >= r) return addtag2(x, k);pushdown(x);if(L <= mid) add(L, R, k, ls(x), l, mid );if(R > mid) add(L, R, k, rs(x), mid+1, r);val[x] = min(val[ls(x)], val[rs(x)]);return;
}
inline int query(int L, int R, int x = 1, int l = 1, int r = n){if(val[x] > 0) return n+1;if(l == r) return l;pushdown(x);if(R <= mid) return query(L, R, ls(x), l, mid );if(L > mid) return query(L, R, rs(x), mid+1, r);int res1 = query(L, R, ls(x), l, mid);if(res1 == n+1) return query(L, R, rs(x), mid+1, r);else return res1;
}
inline void clear(){return addtag1(1);
}
#ifdef DEBUG
inline int getval(int pos, int x = 1, int l = 1, int r = n){if(l == r) return val[x];pushdown(x);if(pos <= mid) return getval(pos, ls(x), l, mid );else return getval(pos, rs(x), mid+1, r);
}
#endifint sta1[N], top1; // Max
int sta2[N], top2; // Minint main(){read(n, k, d);for(int i = 1; i <= n; ++i) read(a[i]);if(d == 0){for(int l = 1, r = 1; l <= n; l = r){while(r <= n && a[l] == a[r]) ++r;if(r-l > ans) ans = r-l, ansl = l;}}else{for(int i = 1; i <= n; ++i) b[i] = div(a[i]);for(int l = 1, r = 1; l <= n; l = r){while(r <= n && mod(a[r]) == mod(a[l])) ++r;clear(), add(l, r-1, 1-k);top1 = top2 = 0;sta1[0] = sta2[0] = l-1;vis.clear();for(int i = l, j = l; i < r; ++i){add(l, i, -1);#ifdef DEBUGcerr << i << " valnow1:" << getval(3) << endl;#endifsta1[top1+1] = sta2[top2+1] = i;while(top1 && b[sta1[top1]] <= b[i]) add(sta1[top1-1]+1, sta1[top1], -b[sta1[top1]]), --top1;while(top2 && b[sta2[top2]] >= b[i]) add(sta2[top2-1]+1, sta2[top2], b[sta2[top2]]), --top2;#ifdef DEBUGcerr << i << " valnow2:" << getval(3) << endl;#endifadd(sta1[top1]+1, i, b[i]), add(sta2[top2]+1, i, -b[i]);sta1[++top1] = sta2[++top2] = i;while(vis[b[i]]) --vis[b[j++]];++vis[b[i]];#ifdef DEBUGcerr << i << " valnow3:" << getval(3) << endl;#endifint pos = query(j, i);if(i-pos+1 > ans) ans = i-pos+1, ansl = pos;}}}write(ansl, ' ', ansl+ans-1);return 0;
}
CF773E Blog Post Rating
首先发现 \(a_i\) 从小到大排列最优，因为交换相邻位置不劣。
然后考虑 rating 的变化。发现 rating 是先单调下降再单调不降。下面定义在已经选择的数中，不大于 \(x\) 的数的数量为 \(c_x\)。
发现单调不降时的限制形如 \(ans \le i+(len-c_i)\)，整理得 \(ans \le len+(i-c_i)\)。这个是容易维护的。然后考虑寻找拐点，发现拐点是第一个不降的点，而不降的条件是 \(c_i > -i\)。于是我们线段树二分出拐点然后区间 min 即可。
#include <bits/stdc++.h>
#define llong long long
#define N 500005
using namespace std;constexpr int inf = 1e9+7;
constexpr int m = 500005;int n;
int a[N];int val[N<<3], siz[N<<3], tag[N<<3];
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
#define mid ((l+r)>>1)
#define pushup(x) (val[x] = min(val[ls(x)],val[rs(x)]), siz[x] = siz[ls(x)]+siz[rs(x)])
#define addtag(x,k) (val[x] -= k, tag[x] += k)inline void build(int x = 1, int l = -m, int r = m){#ifdef DEBUG// cerr << l << " " << r << "\n";#endifif(l == r) return val[x] = l, void();build(ls(x), l, mid), build(rs(x), mid+1, r);pushup(x);return;
}
inline void pushdown(int x){if(!tag[x]) return;addtag(ls(x), tag[x]), addtag(rs(x), tag[x]);tag[x] = 0;return;
}
inline void insert(int pos, int x = 1, int l = -m, int r = m){if(l == r) return ++siz[x], void();pushdown(x);if(pos <= mid) insert(pos, ls(x), l, mid );else insert(pos, rs(x), mid+1, r);pushup(x);return;
}
inline void add(int L, int R, int k, int x = 1, int l = -m, int r = m){if(L <= l && R >= r) return addtag(x, k), void();pushdown(x);if(L <= mid) add(L, R, k, ls(x), l, mid );if(R > mid) add(L, R, k, rs(x), mid+1, r);pushup(x);return;
}
inline int getrnk(int k, int x = 1, int l = -m, int r = m){if(l == r) return siz[x];if(k <= mid) return getrnk(k, ls(x), l, mid);else return siz[ls(x)]+getrnk(k, rs(x), mid+1, r);
}
inline int getmin(int L, int R, int x = 1, int l = -m, int r = m){if(!x) return inf;if(L <= l && R >= r) return val[x];pushdown(x);if(R <= mid) return getmin(L, R, ls(x), l, mid );if(L > mid) return getmin(L, R, rs(x), mid+1, r);return min(getmin(L, R, ls(x), l, mid), getmin(L, R, rs(x), mid+1, r));
}
inline int getfst(int x = 1, int l = -m, int r = m, int now = 0){if(-(now+siz[x]) > r) return -m-1;if(l == r) return l;int res = getfst(ls(x), l, mid, now);return res == -m-1 ? getfst(rs(x), mid+1, r, now+siz[ls(x)]) : res;
}int main(){ios::sync_with_stdio(false);cin >> n;build();val[0] = inf;for(int i = 1; i <= n; ++i){cin >> a[i];add(a[i], m, 1), insert(a[i]);int pos = getfst();cout << i+getmin(pos, m) << endl;}return 0;
}