1 条题解
-
1
居然没人发题解,那我发个吧
推出来一个挺复杂的线段树,没想到竟然是正解。
我们枚举大小为**\(x\)的数,那么如果在区间\([L, R]\)中,\(x\)符合题目的条件,记\(num[i]\)为\(1\)到\(i\)中\(x\)的出现次数,那么有\(\frac{num[R] - num[L - 1]}{R - L + 1} > \frac1{2}\),整理得$$2num[R] - R > 2num[L - 1] - (L - 1)$$ 所以我们令\(b[i] = 2num[i] - i\),就变成了要统计\(b[j] < b[i](j < i)\)**的个数了。
随便用什么数据结构维护,对于大小为**\(x\)的数的统计,大概能达到\(O(n^2logn)\)**的复杂度。
但每次从**\(1\)到\(n\)扫一遍当然不行,所以我们想,能不能只遍历\(x\)**出现的位置。
记**\(i\)为\(x\)这一次出现的位置,\(nxt[i]\)为\(x\)下一次出现的位置,那么我们要快速的找到所有的\(j\),满足\(b[j] < b[i], j < i, i \in [i, nxt[i] - 1]\)**.
对于**\((i, nxt[i] - 1]\)中的\(b[i]\),有\(b[i] = b[i - 1] - 1\),那么要查询的实际是连续的一段前缀和,即\(sum[b[i]], sum[b[i]-1], \cdots, sum[b[i] - (nxt[i] - i - 1)]\)**.
因为还要有修改,遂启发我们用线段树维护前缀和,即每个节点维护小于等于右端点的所有数的和。
那么上述的询问就相当于对区间**\([b[i] - (nxt[i] - i - 1) - 1, b[i] - 1]\)**进行查询。
而修改,如果加入一个数**\(t\),因为维护的是前缀和,要对区间\([t, n]\)都加\(1\)。但是现在我们应该把\([i, nxt[i] - 1]\)的贡献全部加入线段树中,即将区间\([b[i], n],[b[i] - 1, n], \cdots, [b[i] - (nxt[i] - i), n]\)全部加\(1\)**。
稍微想一下,会发现,其实是将区间**\([b[i] - (nxt[i] - i), b[i]]\)加一个首项为1的等比数列,再将区间\([b[i] + 1, n]\)加\(nxt[i] - i\)**.所以线段树要支持区间加和区间加等差数列,以及求区间和。
加等比数列,转换成绝对下标即可,维护一个一次函数
而已#include<cstdio> #include<iostream> #include<cmath> #include<algorithm> #include<cstring> #include<cstdlib> #include<cctype> #include<vector> #include<queue> #include<assert.h> #include<ctime> using namespace std; //#define int long long #define enter puts("") #define space putchar(' ') #define Mem(a, x) memset(a, x, sizeof(a)) #define In inline #define forE(i, x, y) for(int i = head[x], y; ~i && (y = e[i].to); i = e[i].nxt) typedef long long ll; typedef double db; const int INF = 0x3f3f3f3f; const db eps = 1e-8; const int maxn = 5e5 + 5; In ll read() { ll ans = 0; char ch = getchar(), las = ' '; while(!isdigit(ch)) las = ch, ch = getchar(); while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar(); if(las == '-') ans = -ans; return ans; } In void write(ll x) { if(x < 0) x = -x, putchar('-'); if(x >= 10) write(x / 10); putchar(x % 10 + '0'); } int n, a[maxn]; int pos[maxn], nxt[maxn]; struct Tree { int l, r; bool cl; ll lzi, lzy, sum; In void Clear() { cl = 1; lzi = lzy = sum = 0; } }t[maxn << 3]; In void build(int L, int R, int now) { t[now].l = L, t[now].r = R; if(L == R) return (void)t[now].Clear(); int mid = (L + R) >> 1; build(L, mid, now << 1), build(mid + 1, R, now << 1 | 1); } In void Change(int now, ll d1, ll d2) { int len = t[now].r - t[now].l + 1; t[now].lzi += d1; t[now].sum += (d1 * (1LL * t[now].l + t[now].r) * len >> 1); t[now].lzy += d2; t[now].sum += d2 * len; } In void pushdown(int now) { if(t[now].cl) t[now << 1].Clear(), t[now << 1 | 1].Clear(), t[now].cl = 0; if(t[now].lzi || t[now].lzy) { Change(now << 1, t[now].lzi, t[now].lzy); Change(now << 1 | 1, t[now].lzi, t[now].lzy); t[now].lzi = t[now].lzy = 0; } } In void update(int L, int R, int now, int d1, int d2) { if(L > R) return; if(t[now].l == L && t[now].r == R) { Change(now, d1, d2); return; } pushdown(now); int mid = (t[now].l + t[now].r) >> 1; if(R <= mid) update(L, R, now << 1, d1, d2); else if(L > mid) update(L, R, now << 1 | 1, d1, d2); else update(L, mid, now << 1, d1, d2), update(mid + 1, R, now << 1 | 1, d1, d2); t[now].sum = t[now << 1].sum + t[now << 1 | 1].sum; } In ll query(int L, int R, int now) { if(t[now].l == L && t[now].r == R) return t[now].sum; pushdown(now); int mid = (t[now].l + t[now].r) >> 1; if(R <= mid) return query(L, R, now << 1); else if(L > mid) return query(L, R, now << 1 | 1); else return query(L, mid, now << 1) + query(mid + 1, R, now << 1 | 1) ; } In ll solve(int p) { nxt[0] = p; int x = 0, num = 0; ll ret = 0; while(x <= n) { if(x > 0) num++; int val = (num << 1) - x, tp = nxt[x] - x - 1; ret += query(val - tp - 1, val - 1, 1); update(val - tp, val, 1, 1, -(val - tp - 1)); update(val + 1, n, 1, 0, tp + 1); x = nxt[x]; } t[1].Clear(); return ret; } int main() { n = read(); int TYPE = read(); for(int i = 1; i <= n; ++i) a[i] = read(), pos[i - 1] = n + 1; for(int i = n; i; --i) nxt[i] = pos[a[i]], pos[a[i]] = i; Mem(pos, 0); //重复利用 build(-n, n, 1); ll ans = 0; for(int i = 1; i <= n; ++i) if(!pos[a[i]]) ans += solve(i), pos[a[i]] = 1; write(ans), enter; return 0; }
- 1
信息
- ID
- 120
- 时间
- 4000ms
- 内存
- 500MiB
- 难度
- 5
- 标签
- 递交数
- 23
- 已通过
- 14
- 上传者