Hangdian Multi-School-Loop-(uncertainty greedy + line segment tree)

Loop

题意：
就是给你一个数组,Then you can operatek次,Each can choose two Numbersl和r,让va[l]插到va[r]的后面.Then ask you to operatek次后,What is the maximum lexicographical order of this array.

思考：
1.One number can be inserted at the back at a time,Then let you find the largest lexicographical order,Then I'm sure that the front one can be as big as possible.So the first one can be changed from[1,k+1]This interval takes a maximum value to become the first number,because you can put the frontkthrow them all behind.So every time I can take the maximum value of a certain interval as the previous one,The numbers in front of the maximum value are thrown behind,No matter where you throw it.
2.For the throw points I put them in a sequence,Then it has been processed from front to back,until the last number is processed.Now get two sequences,One is a sequence of fixed maximum values ​​each time,One is the sequence of numbers I throw away.Then I can iterate through the sequence of maximum values ​​from front to back,If the number of sequences I throw away is greater than the number currently traversed,Then I can put this number first,Because every time I go back,I'll leave it here.
3.But then I thought,Is it possible that it should still be here?？should still be ahead,其实不会,Because the first time you went[1,k+1]的最大值,Then this number of yours will definitely not appear in the front.So don't worry about this.
4.For every time you can[i,i+k-1]This period of interval for maximum,If every time looking for a timeout violence,I can first maintain the maximum value with a line segment tree.然后维护n个set,每个setis where each digit appears.我就可以在s[maxn]找到第一个>=i的位置,Why is the first,Because I deal with the first one and it's enough,剩下的k留给后面的.This finds the position of the maximum value.牛客练习赛85-哲学家的沉思,This topic is also used for this operation.
5.when outputting the answer,If the current value of the fixed sequence>=Throw away the maximum value of the sequence,I am the first output？To output the value of the current fixed sequence first,Because the maximum number of throws is so large,But behind fixed sequence of maximum might have a bigger,So here is the detail.
6.还有一点就是,当k非常大的时候,if not usek,Its practical tube,我就选l==rAfter the operation is not operating.如果r必须>l.Then it is necessary to determine whether there are adjacent identical values ​​in the answer array,let them change,如果没有,I'll replace the last two untilk为0.

代码：

 #include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define db double
#define int long long
#define PII pair<int,int >
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define node_l node<<1
#define node_r node<<1|1

using namespace std;
const int mod = 1e9+7,inf = 1e18;
const int N = 1e6+10,M = 2010;

int T,n,m,k;
int va[N];
int vb[N];
int vc[N];
int cnt1,cnt2;
set<int > s[N];

struct seg_max{
    
    struct node{
    
        int L,R;
        int maxn;
    }t[4*N];
    void pushup(int node)
    {
    
        t[node].maxn = max(t[node_l].maxn,t[node_r].maxn);
    }
    void build(int node,int l,int r)
    {
    
        t[node].L = l,t[node].R = r;
        t[node].maxn = -inf; //Multiple tree-building initialization details,虽然会被pushup更新,但是有时候没有pushup的时候,就会错,So just initialize it all
        if(l==r)
        {
    
            t[node].maxn = va[l];
            return ;
        }
        int mid = (l+r)>>1;
        build(node_l,l,mid);build(node_r,mid+1,r);
        pushup(node);
    }
    void update(int node,int l,int r,int value)
    {
    
        if(t[node].L>=l&&t[node].R<=r)
        {
    
            t[node].maxn = max(t[node].maxn,value);
            return ;
        }
        int mid = (t[node].L+t[node].R)>>1;
        if(r<=mid) update(node_l,l,r,value);
        else if(l>mid) update(node_r,l,r,value);
        else update(node_l,l,mid,value),update(node_r,mid+1,r,value);
        pushup(node);
    }
    int query(int node,int l,int r)
    {
    
        if(t[node].L>=l&&t[node].R<=r) return t[node].maxn;
        int mid = (t[node].L+t[node].R)>>1;
        if(r<=mid) return query(node_l,l,r);
        else if(l>mid) return query(node_r,l,r);
        else return max(query(node_l,l,mid),query(node_r,mid+1,r));
        pushup(node);
    }
}t_max;

void solve()
{
    
    cnt1 = 0,cnt2 = 0;
    for(int i=1;i<=n;i++)
    {
    
        int l = i,r = min(n,i+m);
        int maxn = t_max.query(1,l,r); //这段区间的最大值
        int idx = *s[maxn].lower_bound(l); //第一个出现的位置
        vb[++cnt1] = va[idx];
        for(int j=i;j<idx;j++) vc[++cnt2] = va[j];
        m -= idx-i;
        i = idx;
    }
    sort(vc+1,vc+1+cnt2,greater<int>());
    vector<int > anw;
    int i = 1,j = 1;
    while(i<=cnt1||j<=cnt2)
    {
    
        if(i>cnt1)
        {
    
            anw.pb(vc[j++]);
            continue;
        }
        if(j>cnt2)
        {
    
            anw.pb(vb[i++]);
            continue;
        }
        if(vb[i]>=vc[j]) anw.pb(vb[i++]); //Or take a fixed sequence
        else anw.pb(vc[j++]);
    }
    for(int i=0;i<anw.size();i++)
    {
    
        cout<<anw[i];
        if(i!=anw.size()-1) cout<<" ";
    }
    cout<<"\n";
}

signed main()
{
    
    IOS;
    cin>>T;
    while(T--)
    {
    
        cin>>n>>m;
        for(int i=1;i<=n;i++) cin>>va[i];
        t_max.build(1,1,n);
        for(int i=1;i<=t_max.query(1,1,n);i++) s[i].clear(); //初始化
        for(int i=1;i<=n;i++) s[va[i]].insert(i);
        solve();
    }
    return 0;
}

总结：
多多思考,注意细节.