题目链接
一、题意
给你个数的序列，问你区间内每个数的出现次数是的区间个数。
数据范围：
二、题解
学习的是tourist的代码。
大致做法是从右到左枚举左端点，然后区间查询合法右端点的个数。
右端点的值是表示合法，表示不合法，那么区间询问最小值和最小值的个数，如果最小值是，答案累加最小值的个数即可。
具体说下怎么维护区间右端点。
设区间左端点是，区间右端点是。
从右到左枚举，只会影响和有关的区间。对答案有贡献的是个数是的区间。
具体细节看下图和代码。
三、代码
#include<bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define sz(x) (int)x.size()
#define cl(x) x.clear()
#define all(x) x.begin() , x.end()
#define rep(i , x , n) for(int i = x ; i <= n ; i ++)
#define per(i , n , x) for(int i = n ; i >= x ; i --)
#define mem0(x) memset(x , 0 , sizeof(x))
#define mem_1(x) memset(x , -1 , sizeof(x))
#define mem_inf(x) memset(x , 0x3f , sizeof(x))
#define debug(x) cerr << #x << " = " << x << '\n'
#define ddebug(x , y) cerr << #x << " = " << x << " " << #y << " = " << y << '\n'
#define ios std::ios::sync_with_stdio(false) , cin.tie(0)
using namespace std ;
typedef long long ll ;
typedef long double ld ;
typedef pair<int , int> pii ;
typedef pair<ll , ll> pll ;
typedef double db ;
const int mod = 998244353 ;
const int maxn = 5e5 + 10 ;
const int inf = 0x3f3f3f3f ;
const double eps = 1e-6 ;
int n , a[maxn] ;
struct seg_tree
{ll mn[maxn << 2] , lazy[maxn << 2] , cnt[maxn << 2] ; int ls(int x){ return x << 1 ; }int rs(int x){ return x << 1 | 1 ; }void push_up(int p){ mn[p] = min(mn[ls(p)] , mn[rs(p)]) ;cnt[p] = 0 ;if(mn[ls(p)] == mn[p]) cnt[p] += cnt[ls(p)] ;if(mn[rs(p)] == mn[p]) cnt[p] += cnt[rs(p)] ;}void build(int id , int l , int r){lazy[id] = 0 ;if(l == r) {mn[id] = 0 , cnt[id] = 1 ; return ;}int mid = (l + r) >> 1 ;build(ls(id) , l , mid) ;build(rs(id) , mid + 1 , r) ;push_up(id) ;} void f(int id , int l , int r , ll k){lazy[id] += k ;mn[id] += k ;}void push_down(int id , int l , int r){int mid = (l + r) >> 1 ;f(ls(id) , l , mid , lazy[id]) ;f(rs(id) , mid + 1 , r , lazy[id]) ;lazy[id] = 0 ;}void add(int id , int l , int r , int x , int y , int k){if(x > y || x > r || y < l) return ;if(x <= l && r <= y){mn[id] += k ;lazy[id] += k ;return ;}push_down(id , l , r) ;int mid = (l + r) >> 1 ;if(x <= mid) add(ls(id) , l , mid , x , y , k) ;if(y > mid) add(rs(id) , mid + 1 , r , x , y , k) ;push_up(id) ;}pll query(int id , int l , int r , int x , int y) //返回区间最小值和最小值的个数{if(x > y || x > r || y < l) return {1e18 , 0} ;pll ans = {1e18 , 0} ;if(x <= l && r <= y) return {mn[id] , cnt[id]} ; int mid = (l + r) >> 1 ;push_down(id , l , r) ;if(x <= mid) {pll res = query(ls(id) , l , mid , x , y) ;if(ans.fi > res.fi) ans = res ;else if(ans.fi == res.fi) ans.se += res.se ;}if(y > mid) {pll res = query(rs(id) , mid + 1 , r , x , y) ;if(ans.fi > res.fi) ans = res ;else if(ans.fi == res.fi) ans.se += res.se ;}return ans ;}
} seg ;
vector<int> pos[maxn] ;
int main()
{ios ;ll ans = 0 ;cin >> n ;rep(i , 1 , n) cin >> a[i] , pos[i].pb(n + 1) ;seg.build(1 , 1 , n) ;per(i , n , 1){int x = a[i] ;int nxt = pos[x].back() ;seg.add(1 , 1 , n , i , nxt - 1 , 1) ;if(sz(pos[x]) >= 4){int third = pos[x][sz(pos[x]) - 3] ;int fourth = pos[x][sz(pos[x]) - 4] ;seg.add(1 , 1 , n , third , fourth - 1 , 1) ;}pos[x].pb(i) ;if(sz(pos[x]) >= 4){int third = pos[x][sz(pos[x]) - 3] ;int fourth = pos[x][sz(pos[x]) - 4] ;seg.add(1 , 1 , n , third , fourth - 1 , -1) ;}pll res = seg.query(1 , 1 , n , i , n) ;if(res.fi == 0) ans += res.se ;}cout << ans << '\n' ;return 0 ;
}