最近思路很混乱，每题都有思路，但是理不清楚

C

这题其实也知道肯定是观察两个相邻的大小关系（排序经典做法）。。但是为什么我在搞暴力讨论枚举。。明明逆序对数目可以直接算。。
不过逆序对相同的要两个元素取min较小的放前面，至于为什么，我不懂啊

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
const int maxn=4e5+10; 
int n,tt,a[maxn];
pair<int,int>pr[maxn];
bool cmp(const pii &x,const pii &y){
    int p=(x.first>y.first)+(x.second>y.second)+(x.first>y.second)+(x.second>y.first);
    int q=(y.first>x.first)+(y.second>x.second)+(y.first>x.second)+(y.second>x.first);
    if(p==q){
        int a=min(x.first,x.second),b=min(y.first,y.second);
        return a<b;
    }
    return p<q;
}
void solve(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>pr[i].first>>pr[i].second;
    sort(pr+1,pr+n+1,cmp);
    for(int i=1;i<=n;i++)cout<<pr[i].first<<' '<<pr[i].second<<' ';
    cout<<endl;
}
signed main(){
    cin>>tt;while(tt--)solve();
}

D

建图题还是不会做，差不多也该会了，不过一开始在想dp想不明白。。建图就是很直观连边的跑最短路。
还有dp做法。这个对我来说比建图难一些。

#include<bits/stdc++.h>
#define fi first
#define se second
#define mkp make_pair
#define pli pair<long long,int>
#define int long long 
using namespace std;
const int maxn=4e5+1000;
int a[maxn],pre[maxn],b[maxn],dis[maxn];
vector<pli>E[maxn];
bool vis[maxn];
void solve(){
    int n;cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i],pre[i]=pre[i-1]+a[i],dis[i]=1e17;
    for(int i=1;i<n;i++)E[i+1].push_back(mkp(0,i));
    for(int i=1;i<=n;i++){
        cin>>b[i];E[i].push_back(mkp(a[i],b[i]));
    }
    priority_queue<pli,vector<pli>,greater<pli> >q;
    q.push(mkp(0,1));
    dis[1]=0;
    while(!q.empty()){
        int v=q.top().second;
        q.pop();
        if(vis[v])continue;
        vis[v]=1;
        for(auto i:E[v]){
            int u=i.second;
            if(dis[u]>dis[v]+i.first){
                dis[u]=dis[v]+i.first;
                q.push(mkp(dis[u],u));
            }
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        //cout<<dis[i]<<endl;
        ans=max(pre[i]-dis[i],ans);
        E[i].clear();vis[i]=0;
    }
    cout<<ans<<endl;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;cin>>t;while(t--)solve();
}

dp做法状态转移是点i走到不大于i的j然后看是否跳到b[j]

#include<bits/stdc++.h>
#define fi first
#define se second
#define mkp make_pair
#define pli pair<long long,int>
#define ll long long
using namespace std;
const int maxn=4e5+1000;
ll f[maxn];
int a[maxn],b[maxn];
vector<int> ed[maxn];
priority_queue<pli> q;
int main() {
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int T;
    cin>>T;
    while (T--) {
        int n;cin>>n;
        for (int i=1;i<=n;i++) f[i]=0;
        for (int i=1;i<=n;i++) {
            cin>>a[i];
            f[i]=f[i-1]+a[i];
        }
        for (int i=1;i<=n;i++) {
            cin>>b[i];
            ed[b[i]].push_back(i);
        }
        for (int i=n-1;i>=1;i--) {
            for (int v:ed[i+1]) {
                if (v<=i) {
                    q.push(mkp(f[i+1]-a[v],v));
                }
            }
            while (!q.empty()) {
                pli p=q.top();
                if (p.se>i) q.pop();
                else {
                    f[i]=max(f[i],p.fi);
                    break;
                }
            }
        }
        while (!q.empty()) q.pop();
        for (int i=1;i<=n;i++) ed[i].clear();
        cout<<f[1]<<'\n';
    }
}