脚本宝典收集整理的这篇文章主要介绍了一些好题，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。
不是很常规的题目。
考虑奶牛之间的相对位置。因为一头奶牛最多跳出来一次，所以两头奶牛的相对位置最多改变两次。这样就可以求出任意两头奶牛的相对位置。
这样的话直接自定义一个比较奶牛的函数然后 sort 一遍就好了。
#include<bits/stdc++.h>
using namespace std;
int n;
int x[20005];
int a[20005][6];
int pos[20005][6];
int s[20005];
bool cmp(int x, int y) {
int cnt = 0;
for (int i = 1; i <= 5; i++)
if (pos[x][i] < pos[y][i]) cnt++;
return cnt >= 3;
}
int main() {
cin >> n;
for (int j = 1; j <= 5; j++)
for (int i = 1; i <= n; i++)
cin >> a[i][j];
for (int i = 1; i <= n; i++) x[i] = a[i][1];
sort(x + 1, x + 1 + n);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= 5; j++)
a[i][j] = lower_bound(x + 1, x + 1 + n, a[i][j]) - x;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= 5; j++)
pos[a[i][j]][j] = i;
for (int i = 1; i <= n; i++) s[i] = i;
sort(s + 1, s + 1 + n, cmp);
for (int i = 1; i <= n; i++)
cout << x[s[i]] << endl;
return 0;
}
相当妙的一道题。
因为这是 Ynoi，所以考虑分块。将 (1-n) 的序列进行分块，设块长为 (sqrt n)。由于一个点的所有祖先的编号都小于这个点，所以维护一下每个点的第一个 不和自己在同一个块内 的祖先 (f)。这样查询 LCA 可以通过类似树链剖分的方式做到 (O(sqrt n))。
再考虑修改。一个块被修改 (sqrt n) 次后，块内每个点的父亲都必定不在当前块内。因此每个点的 (f) 值就是父亲。于是每个块经过 (sqrt n) 次修改就可以直接打懒标记了。那么对于这 (sqrt n) 次修改，考虑 (O(sqrt n)) 暴力重构 (f) 值。这样 (sqrt n) 个块，每个块至多被 (O(sqrt n)) 地重构 (sqrt n) 次，于是这部分的复杂度就做到了 (O(sqrt n))。
总的时间复杂度为 (O(nsqrt n))。
lxl 难得良心一次，本题完全不卡常，代码也很短。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 400005;
int n, m;
int a[maxn];
int l[maxn], r[maxn], pos[maxn];
int t[maxn], cnt[maxn], f[maxn];
int lastans;
int top(int x) {return max(t[x] - f[pos[x]], 1);}
void rebuild(int x) {
for (int i = l[x]; i <= r[x]; i++)
if (a[i] < l[x]) t[i] = a[i];
else t[i] = t[a[i]];
}
void init() {
int block = sqrt(n), g = ceil(n * 1. / block);
for (int i = 1; i <= g; i++) {
l[i] = (i - 1) * block + 1; r[i] = min(i * block, n);
for (int j = l[i]; j <= r[i]; j++) pos[j] = i;
rebuild(i);
}
}
void update(int x, int y, int k) {
int p = pos[x], q = pos[y];
if (p == q) {
for (int i = x; i <= y; i++) a[i] = max(a[i] - k, 1);
rebuild(p);
return;
}
for (int i = p + 1; i <= q - 1; i++) {
if (++cnt[i] >= sqrt(n)) f[i] = min(n, f[i] + k);
else {
for (int j = l[i]; j <= r[i]; j++) a[j] = max(a[j] - k, 1);
rebuild(i);
}
}
for (int i = x; i <= r[p]; i++) a[i] = max(a[i] - k, 1);
for (int i = l[q]; i <= y; i++) a[i] = max(a[i] - k, 1);
rebuild(p); rebuild(q);
}
int query(int u, int v) {
while (1) {
if (u < v) swap(u, v);
if (pos[u] != pos[v]) u = top(u);
else if (top(u) != top(v)) u = top(u), v = top(v);
else break;
}
while (u != v) {
if (u < v) swap(u, v);
u = max(a[u] - f[pos[u]], 1);
}
return u;
}
int main() {
cin >> n >> m;
for (int i = 2; i <= n; i++)
scanf("%d", &a[i]);
init();
for (int i = 1; i <= m; i++) {
int p, x, y, k; scanf("%d", &p);
if (p == 1) {
scanf("%d%d%d", &x, &y, &k);
x ^= lastans; y ^= lastans; k ^= lastans;
update(x, y, k);
} else {
scanf("%d%d", &x, &y);
x ^= lastans; y ^= lastans;
printf("%dn", lastans = query(x, y));
}
}
return 0;
}
因为这是 Ynoi，所以考虑分块。预处理出 (ansl_{i,j}) 表示第 (i) 块的左端点到 (j) 这个区间的逆序对数，(ansr_{i,j}) 表示第 (i) 块的右端点到 (j) 这个区间的逆序对数。预处理的时候用树状数组维护一下，即可做到 (O(1)) 地移动端点。
查询时把区间分成左散块、右散块和中间完整块。用 左散块和中间完整块组成的区间 的逆序对，加上 右散块和中间完整块组成的区间 的逆序对，减去中间完整块的逆序对，再加上左散块对右散块的贡献即可。
显然前三个东西都是可以直接利用 (ans) 求的。而最后一个东西，只需要在预处理的时候保存块内排序的结果，然后归并扫一遍即可。
时空复杂度均为 (O(nsqrt n))。
本题卡常，考虑 IO 优化，再瞎调块长，卡卡过掉了。
但不保证任何时刻都能通过此题。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 1e5 + 5, maxb = 205;
int n, m, block, t;
ll last;
int a[maxn], st[maxb], ed[maxb], pos[maxn];
int cnt[maxn], pre[maxn], suf[maxn], P1[maxn], P2[maxn];
int c1[maxb][maxn], c2[maxb][maxn];
ll ansl[maxb][maxn], ansr[maxb][maxn];
int qa[maxn], qb[maxn];
int nmsl[20], len;
struct node {
int id, val;
bool operator < (const node &a) const {return val < a.val;}
} b[maxn];
struct BIT {
int sum[maxn];
inline int lowbit(int x) {return x & -x;}
inline void update(int x, int val) {
for (; x <= n; x += lowbit(x))
sum[x] += val;
}
inline int query(int x) {
int res = 0;
for (; x; x -= lowbit(x)) res += sum[x];
return res;
}
} tr;
namespace fastIO {
const int buffer_size = 1024 * 1024 * 40;
char input[buffer_size], output[buffer_size];
char *fin, *fout;
inline void init() {
fread(input, 1, buffer_size, stdin);
fin = input; fout = output;
}
inline void flush() {
fwrite(output, 1, fout - output, stdout);
fflush(stdout);
}
inline int read(int u = 0, char c = *fin++, bool f = false) {
for (; !isdigit(c); c = *fin++) f |= c == '-';
for (; isdigit(c); c = *fin++) u = u * 10 + c - '0';
return f ? -u : u;
}
inline void read(char *s, char c = *fin++) {
for (; !isspace(c); c = *fin++);
for (; isspace(c); c = *fin++) *s++ = c;
*s = '';
}
inline void print(ll u) {
u < 0 ? *fout++ = '-', print(-u) : void(u > 9 ? print(u / 10), *fout++ = u % 10 + '0' : *fout++ = u + '0');
}
inline void print(char *s) {while (*s) *fout++ = *s++; }
inline void print(char c) {*fout++ = c; }
}
using fastIO::read;
using fastIO::print;
inline void init() {
block = 500; t = ceil(n * 1. / block);
for (register int i = 1; i <= t; ++i) {
st[i] = (i - 1) * block + 1; ed[i] = min(i * block, n);
for (register int j = st[i]; j <= ed[i]; ++j) pos[j] = i, b[j] = (node){j, a[j]};
sort(b + st[i], b + ed[i] + 1);
}
for (register int i = 1; i <= t; ++i) {
for (register int j = st[i]; j <= ed[i]; ++j) {pre[j] = tr.query(n) - tr.query(a[j]); tr.update(a[j], 1);}
for (register int j = st[i]; j <= ed[i]; ++j) tr.update(a[j], -1);
for (register int j = ed[i]; j >= st[i]; --j) {suf[j] = tr.query(a[j]); tr.update(a[j], 1);}
for (register int j = ed[i]; j >= st[i]; --j) tr.update(a[j], -1);
P1[st[i]] = P2[ed[i]] = 0;
for (int j = st[i] + 1; j <= ed[i]; ++j) P1[j] = P1[j - 1] + pre[j];
for (int j = ed[i] - 1; j >= st[i]; --j) P2[j] = P2[j + 1] + suf[j];
}
for (register int i = 1, p = 1; i <= n; ++i) {
cnt[a[i]]++;
if (i == ed[p]) {
for (register int j = 1; j <= n; ++j) c1[p][j] = c1[p][j - 1] + cnt[j];
for (register int j = n; j >= 1; --j) c2[p][j] = c2[p][j + 1] + cnt[j];
p++;
}
}
for (register int i = 1; i <= t; ++i) {
for (register int j = st[i]; j <= n; ++j) ansl[i][j] = ansl[i][j - 1] + c2[pos[j] - 1][a[j]] - c2[i - 1][a[j]] + pre[j];
for (register int j = ed[i]; j >= 1; --j) ansr[i][j] = ansr[i][j + 1] + c1[i][a[j]] - c1[pos[j]][a[j]] + suf[j];
}
}
inline ll query(register int l, register int r) {
int x = pos[l], y = pos[r];
if (x == y) {
int p = 1, q = 1, cnt1 = 0, cnt2 = 0; ll ans = ansl[x][r] - ansl[x][l - 1];
for (register int i = st[x]; i <= ed[x]; ++i)
if (b[i].id < l) qa[++cnt1] = b[i].val;
else if (b[i].id <= r) qb[++cnt2] = b[i].val;
while (p <= cnt1 && q <= cnt2)
if (qa[p] <= qb[q]) p++;
else q++, ans -= cnt1 - p + 1;
return ans;
}
int p = 1, q = 1, cnt1 = 0, cnt2 = 0;
ll ans = (y - x > 1 ? ansl[x + 1][r] + ansr[y - 1][l] - ansl[x + 1][st[y] - 1] : P1[r] + P2[l]);
for (register int i = st[x]; i <= ed[x]; ++i)
if (b[i].id >= l) qa[++cnt1] = b[i].val;
for (register int i = st[y]; i <= ed[y]; ++i)
if (b[i].id <= r) qb[++cnt2] = b[i].val;
while (p <= cnt1 && q <= cnt2)
if (qa[p] <= qb[q]) p++;
else q++, ans += cnt1 - p + 1;
return ans;
}
int main() {
fastIO::init();
n = read(); m = read();
for (register int i = 1; i <= n; ++i) a[i] = read();
init();
for (register int i = 1; i <= m; ++i) {
int l = read(), r = read();
l ^= last; r ^= last; last = query(l, r);
printf("%lldn", last);
}
return 0;
}
以上是脚本宝典为你收集整理的一些好题全部内容，希望文章能够帮你解决一些好题所遇到的问题。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。