E题解（反悔贪心。。吧

我看大家都用的dp，也不知道我这个代码是数据太水才过的还是也算是一个正解，因此特发此题解来挨批。

首先我们可以看到，双序***保了同一个数一定有两个数，那么我们可以将这两个数的下标作为一个线段的左右端点，而这两个下标之间的元素之和便是这条线段的权值，那么我们就可以将原问题转换为求 条线段，每条线段都有个权值，从中选择任意的两两不相交的线段，使得所选取的线段权值之和最大。

因此这道题我用的是返回贪心来做的，以右端点进行排序，如果 (左端点）所交的线段权值之和大于 （线段的权值），那么就将 加入进去，如下面代码：

for(int i=1;i<=n;i++){
        int cn=query(q[i].r)-query(q[i].l);
        if(cn<q[i].x){
            add(q[i].r,q[i].x-cn);
            ans+=q[i].x-cn;
        }
    }

前缀和用树状数组维护就行了。 完整代码如下：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<unordered_map>
#include<queue>
using namespace std;
#define int long long
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define MAXN 1000010
#define debug cout<<"&"<<endl
int b[MAXN];
int a[MAXN]; 
int tr[MAXN];
int n;
int p[MAXN];
inline int lowbit(int x){
    return x&-x;
}
void add(int x,int v){
    for(int i=x;i<=2*n;i+=lowbit(i))tr[i]+=v;
}
int query(int x){
    int ans=0;
    for(int i=x;i;i-=lowbit(i))ans+=tr[i];
    return ans;
        
}
struct node{
    int l,r,x;
}q[MAXN];
bool cmp(node a,node b){
    return a.r<b.r;
}
void solve(){
// 	int n;
    cin>>n;
    for(int i=1;i<=2*n;i++){
        cin>>a[i];
    }
    unordered_map<int,int>mp;
    for(int i=1;i<=2*n;i++)b[i]=b[i-1]+a[i];
    int cnt=0;
    for(int i=1;i<=2*n;i++){
        if(mp[a[i]])q[++cnt]={mp[a[i]],i,b[i]-b[mp[a[i]]-1]};
        else mp[a[i]]=i;
    }
    sort(q+1,q+1+n,cmp);
    mp.clear();
    for(int i=1;i<=n;i++){
    	mp[q[i].r]=q[i].x;
	}
    int ans=0;
    int tt=0;
    for(int i=1;i<=n;i++){
    	int cn=query(q[i].r)-query(q[i].l);
    	if(cn<q[i].x){
    		add(q[i].r,q[i].x-cn);
            ans+=q[i].x-cn;
        }
    }
    cout<<ans;
}
signed main(){
	ios;
	int t=1;
// 	cin>>t;
	while(t--)
	solve();
	return 0;
} 

后记：可能是最近贪心题刷的有点多了，看见啥都想贪心一下，然后就想到了反悔贪心，考时没想到完整的证明，可能是非正解，希望大佬点评一下，轻点骂呗qwq。