不相邻集合 64pts
赛时打的用 $ set $ 打的假做法A了，但是没敢交，整了个暴力64pts；
可以发现，对于给定的一个序列，我们只需研究每个数一次就行，因为如果一个数出现多次，答案是不变的；
我们又可以发现，对于一个连续段（比如 1 2 3 4 5 ，其答案最多为 $ \lceil \frac n2 \rceil $ ，其中 $ n $ 为此连续段的长度），所以我们只需动态维护极长连续段的长度即可；
用并查集可以很好维护，每次新加进来一个数的时候分类讨论即可；
时间复杂度：$ \Theta(n \alpha(n)) $；
点击查看代码
#include <iostream>
#include <cstdio>
using namespace std;
int n;
int a[500005];
bool vis[500005];
int fa[500005], siz[500005];
int find(int x) {
if (x != fa[x]) fa[x] = find(fa[x]);
return fa[x];
}
int w(int x, int y) {
if (x % y == 0) return x / y;
else return x / y + 1;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
int ma = -1;
for (int i = 1; i <= n; i++) {
cin >> a[i];
ma = max(ma, a[i]);
}
for (int i = 1; i <= ma; i++) {
fa[i] = i;
siz[i] = 1;
}
int ans = 1;
cout << 1 << ' ';
vis[a[1]] = true;
for (int i = 2; i <= n; i++) {
if (vis[a[i]]) {
cout << ans << ' ';
continue;
}
vis[a[i]] = true;
if (!vis[a[i] - 1] && !vis[a[i] + 1]) {
ans++;
}
if (!vis[a[i] - 1] && vis[a[i] + 1]) {
int x = find(a[i]);
int y = find(a[i] + 1);
ans -= w(siz[y], 2);
fa[x] = y;
siz[y] += siz[x];
ans += w(siz[y], 2);
}
if (vis[a[i] - 1] && !vis[a[i] + 1]) {
int x = find(a[i]);
int y = find(a[i] - 1);
ans -= w(siz[y], 2);
fa[x] = y;
siz[y] += siz[x];
ans += w(siz[y], 2);
}
if (vis[a[i] - 1] && vis[a[i] + 1]) {
int x = find(a[i]);
int y1 = find(a[i] - 1);
int y2 = find(a[i] + 1);
ans -= (w(siz[y1], 2) + w(siz[y2], 2));
fa[x] = y1;
siz[y1] += siz[x];
fa[y1] = y2;
siz[y2] += siz[y1];
ans += w(siz[y2], 2);
}
cout << ans << ' ';
}
return 0;
}
线段树 20pts
暴力20pts；
仔细想想，我们的问题是如何快速求出一个节点的子树的标号和；
不妨设 $ f_{n, x} $ 为一棵有 $ n $ 个叶子的线段树，根的标号是 $ x $ 时的子树和是多少，那么我们不难发现，$ f_{n, x} $ 是关于 $ x $ 的一次函数，且有下列递推式：
\[ f_{n, x} = f_{\lceil \frac n2 \rceil, x << 1} + f_{\lfloor \frac n2 \rfloor, x << 1 | 1} \]我们用一次函数的通用表达形式表达出此递推式，可得出 $ k $ 和 $ b $ 的递推式，记忆化搜索即可；
点击查看代码
#include <iostream>
#include <cstdio>
#include <map>
using namespace std;
const long long mod = 1e9 + 7;
int t;
long long n, x, y;
map<long long, long long> k;
map<long long, long long> b;
inline long long ls(long long x) {
return x << 1;
}
inline long long rs(long long x) {
return x << 1 | 1;
}
long long w(long long a, long long b) {
if (a % b == 0) return a / b;
else return a / b + 1;
}
long long K(long long x) {
if (k[x]) return k[x];
if (x == 0) return 0;
return k[x] = (2 * (K(w(x, 2)) + K(x / 2) % mod) % mod + 1) % mod;
}
long long B(long long x) {
if (b[x] || x == 1) return b[x];
if (x == 0) return 0;
return b[x] = (B(w(x, 2)) + B(x / 2) % mod + k[x / 2] % mod);
}
long long ask(long long id, long long L, long long R, long long l, long long r) {
if (L >= l && R <= r) {
return (k[R - L + 1] * (id % mod) % mod + b[R - L + 1]) % mod;
}
long long mid = (L + R) >> 1;
if (r <= mid) return ask(ls(id), L, mid, l, r);
else if (l > mid) return ask(rs(id), mid + 1, R, l, r);
else return (ask(ls(id), L, mid, l, mid) + ask(rs(id), mid + 1, R, mid + 1, r)) % mod;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> t;
while(t--) {
cin >> n >> x >> y;
k.clear();
b.clear();
k[1] = 1;
b[1] = 0;
K(n);
B(n);
cout << ask(1, 1, n, x, y) << '\n';
}
return 0;
}