【题目大意】
求有多少区间只包含1个出现次数为1的数。
$1leq n leq 5*10^5, 0 leq a_i leq 10^9$
【题解】
考虑枚举右端点，设这个数上一次出现位置为pre[i]，那么就是$[pre[i]+1,i]$区间加1，$[pre[pre[i]]+1, pre[i]]$区间减1，和统计区间中1的个数。
注意到数不会减到负的，那么1只可能是最小值或次小值，那么线段树直接维护即可。
复杂度$O(nlogn)$。
考场交错代码导致爆0...QAQ
# include <vector> # include <stdio.h> # include <string.h> # include <iostream> # include <algorithm> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef long double ld; const int M = 5e5 + 10, N = 1e5 + 10, inf = 1e9; inline int getint() { int x = 0; char ch = getchar(); while(!isdigit(ch)) ch = getchar(); while(isdigit(ch)) x = (x<<3) + (x<<1) + ch - '0', ch = getchar(); return x; } int n, m, a[M], pre[M], lst[M]; vector<int> ps; struct pa { int x, tx, y, ty; pa() {} pa(int x, int tx, int y, int ty) : x(x), tx(tx), y(y), ty(ty) {} inline friend pa operator + (pa a, pa b) { pa c; if(a.x < b.x) { c.x = a.x, c.tx = a.tx; c.y = min(a.y, b.x); c.ty = 0; if(a.y == c.y) c.ty += a.ty; if(b.x == c.y) c.ty += b.tx; } else if(a.x > b.x) { c.x = b.x, c.tx = b.tx; c.y = min(a.x, b.y); c.ty = 0; if(a.x == c.y) c.ty += a.tx; if(b.y == c.y) c.ty += b.ty; } else { c.x = a.x, c.tx = a.tx + b.tx; c.y = min(a.y, b.y); c.ty = 0; if(a.y == c.y) c.ty += a.ty; if(c.y == b.y) c.ty += b.ty; } return c; } }; struct SMT { pa w[M << 2]; int tag[M << 2]; # define ls (x<<1) # define rs (x<<1|1) inline void up(int x) { w[x] = w[ls] + w[rs]; } inline void pushtag(int x, int t) { w[x].x += t; if(w[x].y != inf) w[x].y += t; tag[x] += t; } inline void down(int x) { if(!tag[x]) return ; pushtag(ls, tag[x]); pushtag(rs, tag[x]); tag[x] = 0; } inline void build(int x, int l, int r) { if(l == r) { w[x].x = 0, w[x].tx = 1; w[x].y = inf, w[x].ty = 0; return ; } int mid = l+r >> 1; build(ls, l, mid); build(rs, mid+1, r); up(x); } inline void edt(int x, int l, int r, int L, int R, int d) { if(L <= l && r <= R) { pushtag(x, d); return ; } down(x); int mid = l+r>>1; if(L <= mid) edt(ls, l, mid, L, R, d); if(R > mid) edt(rs, mid+1, r, L, R, d); up(x); } inline pa sum(int x, int l, int r, int L, int R) { if(L <= l && r <= R) return w[x]; down(x); int mid = l+r>>1; if(R <= mid) return sum(ls, l, mid, L, R); else if(L > mid) return sum(rs, mid+1, r, L, R); else return sum(ls, l, mid, L, mid) + sum(rs, mid+1, r, mid+1, R); } inline void debug(int x, int l, int r) { printf("x = %d,l = %d,r = %d,mi = %d,semi = %d,minum = %d,seminum = %d,tag = %d ", x, l, r, w[x].x, w[x].y, w[x].tx, w[x].ty, tag[x]); if(l == r) return ; int mid = l+r>>1; debug(ls, l, mid); debug(rs, mid+1, r); } }T; int main() { freopen("a1.in", "r", stdin); // freopen("a.out", "w", stdout); n = getint(); for (int i=1; i<=n; ++i) { a[i] = getint(); ps.push_back(a[i]); } sort(ps.begin(), ps.end()); ps.erase(unique(ps.begin(), ps.end()), ps.end()); m = ps.size(); for (int i=1; i<=n; ++i) a[i] = lower_bound(ps.begin(), ps.end(), a[i]) - ps.begin() + 1; for (int i=1; i<=n; ++i) pre[i] = lst[a[i]], lst[a[i]] = i; ll ans = 0; pa t; T.build(1, 1, n); for (int i=1; i<=n; ++i) { // T.debug(1, 1, n); cout << endl; T.edt(1, 1, n, pre[i] + 1, i, 1); if(pre[i]) T.edt(1, 1, n, pre[pre[i]] + 1, pre[i], -1); t = T.sum(1, 1, n, 1, i); if(t.x == 1) ans += t.tx; if(t.y == 1) ans += t.ty; // 区间加1，区间减1，查询区间内1的出现次数 } cout << ans; return 0; }