10月30日解题报告

做题思路
第一题表示根本没有想到是线段树这种东西，结果看到题解的时候。。。内心是崩溃的，看了线段树还是得多练练，第二题是dp，算是简单，但是自己没有想到还是很伤，也还是要多练，感觉这两个直接踩到我的痛点了
总分 300
得分 第一题（线段树）：40分，第二题（dp）：0分，第三题（字典树）：0分，惨不忍睹

第一题
给定一个由小写字母组成的字符串 s。有 m 次操作,每次操作给定 3 个参数 l,r,x。如果 x=1,将 s[l]~s[r]升序排序;如果 x=0,将 s[l]~s[r]降序排序。你需要求出最终序列。

样例输入:
5 2
cabcd
1 3 1
3 5 0
样例输出:
abdcc

AC思路：
标程TLE了是真的尴尬。。。所以求助于组内大佬，得到真传。。。我们可以建一颗裸的线段树，把各个叶子节点附上对应位置字符-‘a’+1的值，（因为初始是0，如果不+1后面会搞事情），然后对于一个节点，如果其两个子节点的数值相同，那么它自己也附上相同的值。。。这样输出或求个数时就不一定要把树给遍历完了，而且其也承担着懒数组（伪）的作用，更改时如果区间不完全重合，那么就需要把其子孩子附上它的值（有可能之前的更改没有变更它的值，再把它清0）,然后对于每一次操作，求其区间内各个字母的次数，然后按照要求从a-z或从z-a循环，如果有则将相应区间内原来值替换，就搞定了，输入和建树差不多，直接输出就可以了;
代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
int n,m;
char s[200000];
string ds;
struct node
{
    int l,r;
    int a;
}e[400000];
int w[30];
int read()
{
    int x=0,y=1;char k;
    while(k<'0'||k>'9'){if(k=='-')y=-1;k=getchar();}
    while(k>='0'&&k<='9'){x=(x<<3)+(x<<1)+k-'0';k=getchar();}
    return x*y;
}
int build(int ll,int rr,int u)
{
    e[u].l=ll;
    e[u].r=rr;
    if(ll==rr)
    {
        e[u].a=(int)(s[ll]-'a'+1);
        return 0;
    }
    int mid=(ll+rr)>>1;
    build(ll,mid,u<<1);
    build(mid+1,rr,u<<1|1);
    if(e[u<<1].a==e[u<<1|1].a)
        e[u].a=e[u<<1].a;
}
void getsum(int ll,int rr,int u)
{
    if(e[u].l>=ll&&e[u].r<=rr&&e[u].a)
    {
        w[e[u].a]+=e[u].r-e[u].l+1;
        return;
    }
    if(e[u].a)e[u<<1].a=e[u].a,e[u<<1|1].a=e[u].a;
    int mid=(e[u].l+e[u].r)>>1;
    if(mid>=ll)getsum(ll,rr,u<<1);
    if(mid<rr)getsum(ll,rr,u<<1|1);
}
void th(int ll,int rr,int u,int x)
{
    if(e[u].l>=ll&&e[u].r<=rr||e[u].a==x)
    {
        e[u].a=x;
        return; 
    }
    if(e[u].a)e[u<<1].a=e[u].a,e[u<<1|1].a=e[u].a,e[u].a=0;
    int mid=(e[u].l+e[u].r)>>1;
    if(mid>=ll)th(ll,rr,u<<1,x);
    if(mid<rr)th(ll,rr,u<<1|1,x);
    if(e[u<<1].a==e[u<<1|1].a)
        e[u].a=e[u<<1].a;
}
void shuchu(int u)
{
    if(e[u].a)
    {
        for(int i=1;i<=e[u].r-e[u].l+1;++i)
            cout<<(char)('a'+e[u].a-1);
        return;
    }
    shuchu(u<<1);
    shuchu(u<<1|1);
}
int main()
{
    n=read();m=read();
    for(int i=1;i<=n;++i)
        cin>>s[i];
    build(1,n,1);
    for(int j=1;j<=m;++j)
    {
        int a,b,x;
        a=read();b=read();x=read();
        for(int i=1;i<=26;++i)
        {
            w[i]=0;
        }
        getsum(a,b,1);
        int l=a;
        if(x==1) 
        for(int i=1;i<=26;++i)
        {
            if(w[i])
            {
                th(l,l+w[i]-1,1,i);
                l=l+w[i];
            } 
        }
        else
        {
            for(int i=26;i>=1;i--)
          {
              if(w[i])
              {
                   th(l,l+w[i]-1,1,i);
                   l=l+w[i];
              } 

          } 
        }
    }
    shuchu(1);  
}

第二题
求出满足以下条件的 n*m 的 01 矩阵个数:
(1) 第 i 行第 1~li 列恰好有 1 个 1。
(2) 第 i 行第 ri~m 列恰好有 1 个 1。
(3) 每列至多有 1 个 1。
输入
第一行两个整数 n,m。接下来 n 行每行 2 个整数 li,ri。
输出
一行一个整数表示答案。对 998244353 取模。
样例输入
2 6
2 4
5 6
样例输出
12
AC思路:
这道题是真的玄学，虽然是dp，但是这道题是用的比较“不合常规”的dp，数从前到后，却代表的是其后面列数的1的个数。。。。搞得我看标程都看了好久（还好有大佬）
好了，回到这道题，我们发现题目除了对哪一行的一个区间内的1的个数有要求外，主要的大前提是每列不能出现多于1个的1，所以我们发现，其实主要是对列有要求，所以dp思路是对列进行。。。我们枚举每一列，对右边排了几个1进行一一地枚举，然后算出方案数，再对左边枚举，再算出方案数，（记得取%）
代码

#include<iostream>
#include<cstdio>
using namespace std;
long long n,m;
long long sl[300000];
long long sr[300000];
long long f[4000][4000];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int l,r;
        cin>>l>>r;
        sl[l]++;
        sr[r]++;
    }
    for(int i=1;i<=m;i++)
       sl[i]+=sl[i-1],sr[i]+=sr[i-1];//前缀和;
    f[0][0]=1;
    for(int i=1;i<=m;i++)//这是枚举的第i列之后,注意不是之前;
    {
        f[i][0]=f[i-1][0];
        for(int j=1;j<=i;j++)//枚举的是已经放了1的个数;
        {
            f[i][j]=(f[i-1][j]+f[i-1][j-1]*(sr[i]-j+1))%998244353;//枚举列与已经放了的个数......倒走.....
        }
        for(int j=sl[i-1];j<sl[i];j++)//不等于是因为等于会有状态重合;
            for(int k=0;k<=i;k++)//枚举左边放置的数量,其实似乎=也可以不要;
            {
               f[i][k]=f[i][k]*(i-k-j)%998244353;//放的方案数
            }
    } 
    cout<<f[m][n];//还是搞不清为什么输出f[m][n];
}