#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
struct segTree{
vector<ll> tree;
vector<pair<ll,bool>> lazy;
int n;
segTree(int _n){
n = _n;
tree.resize(4*(2*n+1)+5) , lazy.resize(4*(2*n+1)+5);
}
void prop(int node,int l,int r){
if(lazy[node].second){
tree[node] = 0;
if(l != r){
lazy[node << 1].second = 1;
lazy[node << 1 | 1].second = 1;
}
lazy[node].second = 0;
lazy[node].first = 0;
return;
}
tree[node] += lazy[node].first * (r - l + 1);
if(l != r){
lazy[node << 1].first += lazy[node].first;
lazy[node << 1 | 1].first += lazy[node].first;
}
lazy[node].first = 0;
}
void update(int node,int l,int r,int lQ,int rQ){
if(l > r) return;
if(lazy[node].first || lazy[node].second) prop(node,l,r);
if(l > rQ || lQ > r) return;
if(lQ <= l && r <= rQ) return lazy[node].first += 1 , prop(node,l,r) , void();
int md = l + r >> 1;
update(node<<1,l,md,lQ,rQ) , update(node<<1|1,md+1,r,lQ,rQ);
tree[node] = tree[node << 1] + tree[node << 1 | 1];
}
ll query(int node,int l,int r,int lQ,int rQ){
if(l > r) return 0;
if(lazy[node].first || lazy[node].second) prop(node,l,r);
if(l > rQ || lQ > r) return 0;
if(lQ <= l && r <= rQ) return tree[node];
int md = l + r >> 1;
return query(node<<1,l,md,lQ,rQ) + query(node<<1|1,md+1,r,lQ,rQ);
}
void clear(){
lazy[1].second = 1;
prop(1,1,2*n+1);
}
void update(int l,int r){
if(l > r) swap(l,r);
update(1,1,2*n+1,l+n+1,r+n+1);
}
ll query(int l,int r){
if(l > r) swap(l,r);
return query(1,1,2*n+1,l+n+1,r+n+1);
}
};
void compress(vector<int> &a){
int n = a.size();
vector<pair<int,int>> b(n);
for(int i=0;i<n;i++){
b[i].first = a[i];
b[i].second = i;
}
sort(b.begin(),b.end());
a[b[0].second] = 1;
int cnt = 1;
for(int i=1;i<n;i++){
if(b[i].first == b[i-1].first){
a[b[i].second] = a[b[i-1].second];
}
else a[b[i].second] = ++cnt;
}
}
void solve(){
int n;
cin>>n;
vector<int> a(n);
for(auto &i:a) cin>>i;
compress(a);
vector<vector<int>> idx(n+1);
for(int i=0;i<n;i++) idx[a[i]].push_back(i);
segTree sg(n);
ll ans = 0;
for(auto v : idx){
if(v.empty()) continue;
int p = 0;
v.push_back(n);
sg.update(p,p-v[0]);
for(int i=0;i<v.size()-1;i++){
p = 2 * i - v[i] + 1;
int cnt = v[i+1] - v[i];
ans += sg.query(-n,p-cnt) * cnt;
if(cnt > 1) ans += sg.query(p-cnt+1,p-1);
sg.update(p,p-cnt+1);
}
sg.clear();
}
cout<<ans<<endl;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int t=1;
//cin>>t;
while(t--){
solve();
}
return 0;
}
Compilation message
Main.cpp: In member function 'void segTree::update(int, int, int, int, int)':
Main.cpp:36:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
36 | int md = l + r >> 1;
| ~~^~~
Main.cpp: In member function 'll segTree::query(int, int, int, int, int)':
Main.cpp:45:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
45 | int md = l + r >> 1;
| ~~^~~
Main.cpp: In function 'void solve()':
Main.cpp:93:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
93 | for(int i=0;i<v.size()-1;i++){
| ~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
65 ms |
30400 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
