题面：https://www.cnblogs.com/Juve/articles/11631298.html

permutation:

参考：https://www.cnblogs.com/clno1/p/10832579.html

因为原来的数组不好做于是我们想反过来数组，根据交换条件：值相邻且位置差大于等于k，那么在变换后的数组就变成了位置相邻且差值大于等于k。这样的话变换操作变成了，相邻的大于等于k的值临近交换，于是我们注意到因为现在只能临近交换的原因，两个差值小于k的数他们的相对位置不可能发生改变。那么问题就变成了，在只有一些相对位置限制条件下，无限制的可以随意交换位置，求这个数组的最小字典序（原数组字典序最小也是现在数组字典序最小）。那么我们容易想到拓扑排序。

但是如果每个点都想后面差值小于k的点连边的话，这个图会变得十分巨大，时间无法承受。于是我们必循得考虑优化建图：我们注意到像a->b,b->c,a->c这种建图，a->c这条边是不必要的。于是我们想办法避免掉这种无意义的边，所以对于某个点，我们让它向后面的所有限制(即差值小于k)中只向最小的那一个点连边，那么用线段树维护这样的信息，这样就达到优化建图的目的。

这样只向最小的连边为什么是对的呢？借用上面大佬的一句话：倒着加入，显然 p_i 连向 (p_i-k, p_i)∪(p_i, p_i+k)。我们只需要分别连向两个区间中下标最小的那一个即可。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<vector>
 6 #include<queue>
 7 using namespace std;
 8 const int MAXN=5e5+5;
 9 int n,k,a[MAXN],pos[MAXN],du[MAXN],ans[MAXN],num=0;
10 vector<int>m[MAXN];
11 priority_queue<int>q;
12 int tr[MAXN<<2];
13 void update(int k,int l,int r,int opt,int val){
14     if(l==r){
15         tr[k]=min(tr[k],val);
16         return ;
17     }
18     int mid=(l+r)>>1;
19     if(opt<=mid) update(k<<1,l,mid,opt,val);
20     else update(k<<1|1,mid+1,r,opt,val);
21     tr[k]=min(tr[k<<1],tr[k<<1|1]);
22 }
23 int query(int k,int l,int r,int opl,int opr){
24     if(opl>opr) return 0x3f3f3f3f;
25     if(opl<=l&&r<=opr) return tr[k];
26     int mid=(l+r)>>1,res=0x3f3f3f3f;
27     if(opl<=mid) res=min(res,query(k<<1,l,mid,opl,opr));
28     if(opr>mid) res=min(res,query(k<<1|1,mid+1,r,opl,opr));
29     return res;
30 }
31 int main(){
32     scanf("%d%d",&n,&k);
33     for(int i=1;i<=n;++i){
34         scanf("%d",&a[i]);
35         pos[a[i]]=i;
36     }
37     memset(tr,0x3f,sizeof(tr));
38     for(int i=n;i>=1;--i){
39         int p=query(1,1,n,max(1,pos[i]-k+1),pos[i]);
40         if(p<=n) m[pos[i]].push_back(pos[p]),++du[pos[p]];
41         p=query(1,1,n,pos[i],min(n,pos[i]+k-1));
42         if(p<=n) m[pos[i]].push_back(pos[p]),++du[pos[p]];
43         update(1,1,n,pos[i],i);
44     }
45     for(int i=1;i<=n;++i){
46         if(!du[i]) q.push(-i);
47     }
48     while(!q.empty()){
49         int x=-q.top();
50         q.pop();
51         ans[x]=++num;
52         int N=m[x].size();
53         for(int i=0;i<N;++i){
54             int y=m[x][i];
55             --du[y];
56             if(!du[y]) q.push(-y);
57         }
58     }
59     for(int i=1;i<=n;++i){
60         printf("%d
",ans[i]);
61     }
62     return 0;
63 }

View Code

tree：

好像是个结论：边权之和就是答案

#include<cstdio>
#define int long long
int n,ans=0;
signed main(){
    scanf("%lld",&n);
    for(int i=1,u,v,w;i<n;++i){
        scanf("%lld%lld%lld",&u,&v,&w);
        ans+=w;
    }
    printf("%lld
",ans);
    return 0;
}

View Code

game：

模拟用堆可以有50分

考虑如何优化

我们对于前p个数找出最大值，并开桶统计所有数出现的次数

然后对于一个新加入的点，如果它大于当前的最大值，那么下一个人一定选择新加如的这个点，所以最大值没有变

否则更新新加入的数的次数并更新最大值

考虑到最大值一定不上升，所以复杂度较有保障

但是还是会T，所以我们离散化一下

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<unordered_map>
#define re register
using namespace std;
const int MAXN=100005;
int n,k,a[MAXN],p,tim[MAXN],cnt,b[MAXN];
signed main(){
    scanf("%d%d",&n,&k);
    for(re int i=1;i<=n;++i) scanf("%d",&a[i]),b[i]=a[i];
    sort(b+1,b+n+1);
    cnt=unique(b+1,b+n+1)-b-1;
    for(int i=1;i<=n;++i) a[i]=lower_bound(b+1,b+cnt+1,a[i])-b;
    while(k--){
        scanf("%d",&p);
        re long long ans1=0,ans2=0;
        re int maxp=0;
        for(re int i=1;i<=p;++i){
            ++tim[a[i]];
            maxp=max(maxp,a[i]);
        }
        ans1+=b[maxp];
        --tim[maxp];
        while(maxp>0&&tim[maxp]==0) --maxp;
        for(re int i=2;i<=n;++i){
            if(i&1){
                if(p+1<=n){
                    ++p;
                    if(a[p]>=maxp) ans1+=b[a[p]];
                    else{
                        ans1+=b[maxp];
                        --tim[maxp];
                        ++tim[a[p]];
                        while(maxp>0&&tim[maxp]==0) --maxp;
                    }
                }else{
                    ans1+=b[maxp];
                    --tim[maxp];
                    while(maxp>0&&tim[maxp]==0) --maxp;
                }
            }else{
                if(p+1<=n){
                    ++p;
                    if(a[p]>=maxp) ans2+=b[a[p]];
                    else{
                        ans2+=b[maxp];
                        --tim[maxp];
                        ++tim[a[p]];
                        while(maxp>0&&tim[maxp]==0) --maxp;
                    }
                }else{
                    ans2+=b[maxp];
                    --tim[maxp];
                    while(maxp>0&&tim[maxp]==0) --maxp;
                }
            }
        }
        printf("%lld
",ans1-ans2);
    }
    return 0;
}

View Code