//雪花飄飄北風嘯嘯
//天地一片蒼茫
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ll,ii>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl;
#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
ll MAX(ll a){return a;}
ll MIN(ll a){return a;}
template<typename... Args>
ll MAX(ll a,Args... args){return max(a,MAX(args...));}
template<typename... Args>
ll MIN(ll a,Args... args){return min(a,MIN(args...));}
#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
int n;
ll arr[200005];
ll pref[200005];
priority_queue<iii> pq;
bool vis[200005];
ll get(int l,int r){
assert(l % 2 = r % 2);
if (r&1) return pref[r]-pref[l-1];
else return pref[l-1]-pref[r];
}
ii range[200005];
int p[200005];
ii merge(ii i,ii j){
return ii(min(i.fi,j.fi),max(i.se,j.se));
}
int parent(int i){
if (p[i]==i) return i;
else return p[i]=parent(p[i]);
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
rep(x,1,n+1){
cin>>arr[x];
pref[x]=pref[x-1]+(x&1?arr[x]:-arr[x]);
pq.push(iii(arr[x],ii(x,x)));
p[x]=x;
range[x]=ii(x,x);
}
ll curr=0;
rep(zzz,0,(n+1)/2){
int l,r;
do{
l=pq.top().se.fi;
r=pq.top().se.se;
pq.pop();
}while (vis[l-1] || vis[r+1]);
vis[l]=true;
vis[r]=true;
curr+=get(l,r);
int node;
if (l==r) node=parent(l);
else{
node=parent(l+1);
p[parent(l)]=node;
p[parent(r)]=node;
range[node]=ii(l,r);
}
if (vis[r+2]){
int temp=parent(r+2);
p[temp]=node;
range[node]=merge(range[node],range[temp]);
}
if (l>1 && vis[l-2]){
int temp=parent(l-2);
p[temp]=node;
range[node]=merge(range[node],range[temp]);
}
l=range[node].fi,r=range[node].se;
if (l!=1 && r!=n){
pq.push(iii(get(l-1,r+1),ii(l-1,r+1)));
}
cout<<curr<<endl;
}
}
Compilation message
In file included from /usr/include/c++/9/ext/pb_ds/detail/pat_trie_/pat_trie_.hpp:45,
from /usr/include/c++/9/ext/pb_ds/detail/container_base_dispatch.hpp:90,
from /usr/include/c++/9/ext/pb_ds/assoc_container.hpp:48,
from candies.cpp:5:
candies.cpp: In function 'long long int get(int, int)':
candies.cpp:42:22: error: lvalue required as left operand of assignment
42 | assert(l % 2 = r % 2);
| ^
