【每日一题】2021年4月9日题目精讲

题号 NC111013
名称 A Simple Task
来源 CF558E
每日一题三期汇总贴~

如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情
欢迎给每日一题投稿，投稿需要提供牛客题库里的题目+题解 投稿有牛币奖励，可发站内信给王清楚或联系QQ 234186389
每日一题QQ群:659028468

题解

作者：小熠小熠很不容易

题意：

给定一个长度不超过10^5的字符串和不超过m次操作。
每个操作 L R K 表示给区间[L,R]的字符串排序，K=1为升序，K=0为降序。
最后输出最终的字符串。

做法：线段树

思路：

根据计数排序的原理，只要知道了有几个数比t小，就可以知道t的位置
这道题只有26个字母，我们只需建26颗线段树
在每次操作时，首先求出这个区间中a~z每个数出现的次数
再分别对每一位字母进行区间覆盖。
对下一个区间进行覆盖要加上之前覆盖的长度
如果是升序排序，我们从a到z依次查询所有线段树，降序就从z到a依次查询
最后遍历整棵线段树输出最终的字符串

代码

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp(aa,bb) make_pair(aa,bb)
#define _for(i,b) for(int i=(0);i<(b);i++)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,b,a) for(int i=(b);i>=(a);i--)
#define mst(abc,bca) memset(abc,bca,sizeof abc)
#define X first
#define Y second
#define lowbit(a) (a&(-a))
#define debug(a) cout<<#a<<":"<<a<<"\n"
typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;
typedef long double ld;
const int N=100010;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const double eps=1e-6;
const double PI=acos(-1.0);

struct Tree{
    bool tag[26];
    int w[26];
    int l,r;
}tree[N<<2];

struct node{
    int v[26];
}zero;

int a[N];

void pushup(int u){
    rep(i,0,25) tree[u].w[i]=tree[u<<1].w[i]+tree[u<<1|1].w[i];
}

void pushdown(int u){
    if(tree[u].l==tree[u].r){
        return;
    }
    rep(i,0,25){
        if(tree[u].tag[i]){
            rep(j,0,25){
                tree[u<<1].tag[j]=0;
                tree[u<<1].w[j]=0;
                tree[u<<1|1].tag[j]=0;
                tree[u<<1|1].w[j]=0;
            }
            tree[u<<1].tag[i]=1;
            tree[u<<1|1].tag[i]=1;
            tree[u<<1].w[i]=tree[u<<1].r-tree[u<<1].l+1;
            tree[u<<1|1].w[i]=tree[u<<1|1].r-tree[u<<1|1].l+1;
            tree[u].tag[i]=0;
        }
    }
}

void build(int l,int r,int u){
    tree[u].l=l,tree[u].r=r;
    if(l==r){
        tree[u].w[a[l]]=1;
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,u<<1);
    build(mid+1,r,u<<1|1);
    pushup(u);
}

void update(int l,int r,int v,int u){
    if(tree[u].l>r||tree[u].r<l){
        return;
    }
    if(l<=tree[u].l&&r>=tree[u].r){
        rep(i,0,25){
            tree[u].w[i]=0;
            tree[u].tag[i]=0;
        }
        tree[u].tag[v]=1;
        tree[u].w[v]=tree[u].r-tree[u].l+1;
        return;
    }
    pushdown(u);
    int mid=(tree[u].l+tree[u].r)>>1;
    if(l<=mid) update(l,r,v,u<<1);
    if(r>mid) update(l,r,v,u<<1|1);
    pushup(u);
}

node query(int l,int r,int u){
    if(l<=tree[u].l&&r>=tree[u].r){
        node t;
        rep(i,0,25){
            t.v[i]=tree[u].w[i];
        }
        return t;
    }
    pushdown(u);
    int mid=(tree[u].l+tree[u].r)>>1;
    node t=zero;
    if(l<=mid){
        node tt=query(l,r,u<<1);
        rep(i,0,25){
            t.v[i]+=tt.v[i];
        }
    }
    if(r>mid){
        node tt=query(l,r,u<<1|1);
        rep(i,0,25){
            t.v[i]+=tt.v[i];
        }
    }
    return t;
}

void print(int u){
    pushdown(u);
    if(tree[u].l==tree[u].r){
        rep(i,0,25){
            if(tree[u].w[i]){
                cout<<(char)('a'+i);
                return;
            }
        }
    }
    print(u<<1);
    print(u<<1|1);
}

void solve(){
    int n,m;cin>>n>>m;
    rep(i,1,n){
        char x;cin>>x;
        a[i]=x-'a';
    }
    build(1,n,1);
    while(m--){
        int l,r,op;cin>>l>>r>>op;
        node t=query(l,r,1);
        if(op){ //升序
            rep(i,0,25){
                update(l,l+t.v[i]-1,i,1);
                l+=t.v[i];
            } 
        }
        else{ //降序
            per(i,25,0){
                update(l,l+t.v[i]-1,i,1);
                l+=t.v[i];
            }
        }
    }
    print(1);
}


int main(){
    ios::sync_with_stdio(0);cin.tie(0);
//    int t;cin>>t;while(t--)
    solve();
    return 0;
}

欢迎各位大佬来做题写题解，也欢迎大家踊跃在当日讨论贴中提问！