本文共 2427 字,大约阅读时间需要 8 分钟。
传送门:
题意:一个1~n的全排列,定义f(i,j,k)为在区间[i,j]内第k大的数,求 ∑nl=1∑nr=lf(l,r,k)
题解:对于每个数求自己对答案的贡献,首先要知道Ai在某个数有贡献当且仅当区间内只有k-1个数比Ai大,于是可以从大到小遍历,这样当枚举到A时,比Ai大的数的位置都已知道,这个可以用set进行保存,然后分别枚举Ai左右两边比Ai大的数的个数以及区间范围。
这个题很卡时间,因此不能用set进行遍历,可以再建立一个领接表来进行O1的遍历
时间复杂度:O(nlogn+nk)
#include#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1using namespace std;typedef long long LL;typedef pair PII;namespace IO {const int MX = 3e7;char buf[MX]; int c, sz;void begin() { c = 0; sz = fread(buf, 1, MX, stdin);}inline bool read(int &t) { while (c < sz && buf[c] != '-' && (buf[c] < '0' || buf[c] > '9')) c++; if (c >= sz) return false; bool flag = 0; if (buf[c] == '-') flag = 1, c++; for (t = 0; c < sz && '0' <= buf[c] && buf[c] <= '9'; c++) t = t * 10 + buf[c] - '0'; if (flag) t = -t; return true;}}const int inf = 0x3f3f3f3f;const int MX = 5e5 + 5;const LL mod = 1e9 + 7;int a[MX], fa[MX];set s;set ::iterator now;struct node { int pre, nxt;} E[MX];int main() { int n, k, T; //freopen("in.txt", "r", stdin); IO::begin(); IO::read(T); while (T--) { IO::read(n); IO::read(k); for (int i = 1; i <= n; i++) { IO::read(a[i]); fa[a[i]] = i; } LL ans = 0; memset(E, -1, sizeof(E)); E[0].nxt = n + 1; E[n + 1].pre = 0; s.clear(); s.insert(0); s.insert(n + 1); for (int i = n; i >= 1; i--) { now = s.upper_bound(fa[i]); //printf("%d %d\n",fa[i],*now); int r = *now; int l = E[*now].pre; s.insert(fa[i]); E[l].nxt = fa[i]; E[r].pre = fa[i]; E[fa[i]].nxt = r; E[fa[i]].pre = l; if (i + k - 1 <= n) { int lc = 0, rc = 1; l = r = fa[i]; int ll = E[l].pre; int rr = E[r].nxt; for (; rc < k && rr != n + 1; rc++, r = E[r].nxt, rr = E[rr].nxt); LL tmp = 0; while (rc > 0) { for (; lc + rc < k && ll != 0; lc++, l = E[l].pre, ll = E[ll].pre); if (lc + rc < k) break; tmp += (LL)(l - ll) * (rr - r) * i; rc--; r = E[r].pre; rr = E[rr].pre; } ans += tmp; } } printf("%lld\n", ans); } return 0;}
转载地址:http://cpwpn.baihongyu.com/