历史和线段树 以XJTU2023 J题为例
/*
* @Author: JorD
* @LastEditTime: 2023-05-25 12:23:35
*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = double;
#define endl '\n'
#define PII pair<ll, ll>
#define siz(s) (ll)(s.size())
#define all(a) a.begin(), a.end()
#define all1(a) a.begin() + 1, a.end()
#define priq priority_queue
#define SPO(n) fixed << setprecision(n)
#define rep(i, l, r) for (ll(i) = (l); (i) <= (r); ++(i))
#define per(i, r, l) for (ll(i) = (r); (i) >= (l); --(i))
#define DBG(n) cout<<"!!! "<<#n<<": "<<n<<'\n'
const int N = 5e5 + 10;
struct Tag{
unsigned add, hadd, tim;
void merge(Tag tmp){
hadd += tmp.hadd + add * tmp.tim;
add += tmp.add;
tim += tmp.tim;
}
};
struct Segtree{
unsigned sum, hsum;
Tag tag;
void update(int len, Tag u){
tag.merge(u);
hsum += u.hadd * len + u.tim * sum;
sum += u.add * len;
}
}tr[N << 2];
void pushdown(int l, int r,int p){
int mid = l + r >> 1;
tr[p << 1].update(mid - l + 1, tr[p].tag);
tr[p << 1|1].update(r - mid, tr[p].tag);
tr[p].tag = {0, 0, 0};
}
void update(int cl, int cr, int l, int r, int p, Tag t){
if(l > cr || r < cl) return;
if(cl <= l && r <= cr){
tr[p].update(r - l + 1, t);
return;
}
int mid = l + r >> 1;
pushdown(l, r, p);
update(cl, cr, l, mid, p << 1, t);
update(cl, cr, mid + 1, r, p << 1|1, t);
tr[p].sum = tr[p << 1].sum + tr[p << 1|1].sum;
tr[p].hsum = tr[p << 1].hsum + tr[p << 1|1].hsum;
}
unsigned query(int cl, int cr, int l, int r, int p){
if(l > cr || r < cl) return 0;
if(cl <= l && r <= cr){
return tr[p].hsum;
}
int mid = l + r >> 1;
pushdown(l, r, p);
return query(cl, cr, l, mid, p << 1) + query(cl, cr, mid + 1, r, p << 1|1);
}
void build(int l, int r, int p){
tr[p] = {0, 0, {0,0,0}};
if(l == r) return;
int mid = l + r >> 1;
build(l, mid, p << 1);
build(mid + 1, r, p << 1|1);
}
int last[N], id[N], a[N];
void Solve(){
int n, m; cin >> n >> m;
rep(i, 1, n){
int x; cin >> x;
a[i] = x;
last[i] = id[x];
id[x] = i;
}
vector<vector<pair<int,int>>> son(n + 1);
rep(i, 1, m){
int l, r; cin >> l >> r;
son[r].push_back({l, i});
}
build(1, n, 1);
vector<unsigned> res(m + 1);
rep(r, 1, n){
update(last[r] + 1, r, 1, n, 1, {1, 0, 0});
update(1, n, 1, n, 1, {0, 0, 1});
for(auto [l, i] : son[r]){
res[i] = query(l, r, 1, n, 1);
}
}
rep(i, 1, m) cout << res[i] << endl;
return;
}
int main(){
std::ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
//int t; cin>>t; while(t --)
Solve();
return 0;
}