A

题意：给定一个\(1\sim n\)的排列，选择一段区间\([l,r]\)，把这段区间翻转一下，使得翻转后排列的字典序最小

\(n\leq 500\)

题解：

由于是排列，所以每一位上的数字各不相同。根据贪心的想法，我们想让这个序列最靠前的地方变得尽可能的小。所以只要找到最靠前的一个位置\(i\)，让我们有比它小的数字，然后用它和它后面最小的数字作为左右端点\(l,r\)，翻转中间部分。

#include<bits/stdc++.h>
using namespace std;
namespace red{
#define int long long
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define lowbit(i) ((i)&(-i))
#define mid ((l+r)>>1)
#define eps (1e-8)
    const int N=1e6+10,mod=1e9+7,inf=2e9;
    int n,pos1,pos2;
    int a[N];
    inline void main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);cout.tie(0);
        int T;cin>>T;
        while(T--)
        {
            cin>>n;
            pos1=n,pos2=0;
            for(int i=1;i<=n;++i)
            {
                cin>>a[i];
                for(int j=1;j<i;++j)
                {
                    if(a[j]>a[i]&&(j<pos1||(j==pos1&&a[i]<a[pos2])))
                    {
                        pos1=j,pos2=i;
                    }
                }
            }
            if(pos2) reverse(a+pos1,a+pos2+1);
            for(int i=1;i<=n;++i) cout<<a[i]<<' ';
            cout<<'\n';
        }
    }
}
signed main()
{
    red::main();
    return 0;   
}
/*

*/

B

题意：

给定一个序列\(A\)，如果相邻两项\(a_i\)和\(a_{i+1}\)奇偶性不同，就可以交换相邻两项，求问能不能通过交换让序列变得不下降（即对任意\(1\leq j<n,a_j<=a_{j+1}\)）

\(n\leq 1e5\)

题解：

对整个序列来说，序列中的所有奇数的相对位置永远不会改变，而奇数和偶数的相对位置可以随意交换。同理，所有偶数的相对位置永远不会改变。

所以只要判断，序列中所有的奇数是不是不下降的，所有的偶数是不是不下降的。

#include<bits/stdc++.h>
using namespace std;
namespace red{
#define int long long
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define lowbit(i) ((i)&(-i))
#define mid ((l+r)>>1)
#define eps (1e-8)
    const int N=1e6+10,mod=1e9+7,inf=2e9;
    int n;
    int a[N];
    int pre[2];
    inline void main()
    {   
        ios::sync_with_stdio(false);
        cin.tie(0);cout.tie(0);
        int T;cin>>T;
        while(T--)
        {
            cin>>n;
            bool flag=1;
            for(int i=1;i<=n;++i) cin>>a[i];
            pre[0]=pre[1]=0;
            for(int i=1;i<=n;++i)
            {
                int b=a[i]&1;
                if(a[i]<pre[b]) flag=0;
                pre[b]=a[i];
            }
            if(flag) cout<<"YES\n";
            else cout<<"NO\n";
        }
    }
}
signed main()
{
    red::main();
    return 0;   
}
/*

*/

C

题意：给定一个序列\(A\)，如果\(i<j\)并且\(a_i>a_j\)，就把\(i\)和\(j\)连起来，问最后一共有几个互不相连的部分？

\(n\leq 2e5\)

题解：

如果暴力去实现这个过程无疑是\(O(n^2)\)的，但是观察暴力连边的过程

这样子，\(<6,1>\)之间很明显不用连边，因为\(6\)的右边有一个\(2\)，它比\(1\)要大，如果\(2\)向\(1\)连了边，\(6\)又向\(2\)连了边，那么\(<6,1>\)这条边就很多余。

所以说，我们每个数字向右需要连边的数字一定是\((2,4,…)\)这样递增的。

那么就用一点技巧来做：倒着遍历这个序列，然后顺便维护一个从\(i+1\)到\(n\)的递增的一个序列。

但是有一点小bug：

如果是\(6,4,7,1\)

那么\(6\)右边递增的序列应该是\(4,7\)

\(6<7\)，所以\(6\)不会向\(7\)连边，但是\(7>1\)，\(6\)本来应该向\(1\)连边的，这里没有\(1\)，而是被\(7\)给挤出去了。

所以应该算一下每一个位置上数字连到数字中的最大值和最小值。

如果现在往右连边的数字的最大值，大于，右边那个数字连到数字的最小值，就可以连。

这样每连一条边，互不相连部分的个数就减一。可以证明每条边都是有用的，不会导致已经联通的部分重复连接。

#include<bits/stdc++.h>
using namespace std;
namespace red{
#define int long long
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define lowbit(i) ((i)&(-i))
#define mid ((l+r)>>1)
#define eps (1e-8)
    const int N=1e6+10,mod=1e9+7,inf=2e9;
    int n;
    int a[N];
    int st[N],top;
    int maxn[N],minn[N],col[N];
    inline void main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);cout.tie(0);
        int T;cin>>T;
        while(T--)
        {
            cin>>n;top=0;
            for(int i=1;i<=n;++i)
            {
                cin>>a[i];
                col[i]=i;
                maxn[i]=minn[i]=a[i];
            }
            int sum=n;
            for(int i=n;i;--i)
            {
                while(top&&maxn[col[i]]>minn[col[st[top]]])
                {
                    maxn[col[st[top]]]=max(maxn[col[i]],maxn[col[st[top]]]);
                    minn[col[st[top]]]=min(minn[col[i]],minn[col[st[top]]]);
                    col[i]=col[st[top]];
                    --top;
                    --sum;
                }
                st[++top]=i;
            }
            cout<<sum<<'\n';
        }
    }
}
signed main()
{
    red::main();
    return 0;   
}
/*

*/

D

题意：有一个\(n*m\)的画布，每次会选一个格子\((x,y)\)，然后把\((x,y),(x+1,y),(x,y+1),(x+1,y+1)\)涂成同一种颜色，后涂的覆盖先涂的，问存不存在一种涂色方法，把画布最后涂成给定的模样。

\(n\leq 1000\)

题解：

因为后来的覆盖先来的，正着涂色要考虑覆盖问题。所以把这个问题倒着做。

问题变成了，每次选一个格子\((x,y)\)，然后把\((x,y),(x+1,y),(x,y+1),(x+1,y+1)\)上的颜色都擦掉，前提是这四个格子中有且仅有一种颜色，问能不能把整个画布上的颜色全擦了。然后把擦颜色的顺序倒着输出出来，就是涂色顺序。

擦颜色就很方便，因为不用考虑后来的覆盖问题，能擦哪里擦哪里就可以。

但是不能每次都把整个画布检查一遍，来决定擦哪里。

我们可以把一开始就能擦的地方放进队列里。然后如果某一个地方，它之前不能擦，而现在能擦了，那么这个地方一定在上一次擦除地方的周围一圈。所以每擦一个地方的颜色，就检查一下周围一圈是不是新出现了可以擦去的地方，可以擦去就放进队列。

因为以每个地方只会擦一次，所以最后复杂度是\(O(n*m)\)的

#include<bits/stdc++.h>
using namespace std;
namespace red{
#define int long long
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define lowbit(i) ((i)&(-i))
#define mid ((l+r)>>1)
#define eps (1e-8)
    const int N=1e6+10,mod=1e9+7,inf=2e9;
    int n,m;
    bool vis[1010][1010];//有没有被擦过
    bool vis2[1010][1010];//是不是以这个格子为基准点擦颜色了
    int a[1010][1010];
    int top;
    struct node
    {
        int x,y,z;
    };
    node st[N];
    queue<node> q;
    inline int check(int i,int j)
    {
        if(i<1||j<1||i>n||j>m) return 0;
        int col=0;
        if(!vis[i][j]) col=a[i][j];
        else if(!vis[i+1][j]) col=a[i+1][j];
        else if(!vis[i][j+1]) col=a[i][j+1];
        else if(!vis[i+1][j+1]) col=a[i+1][j+1];
        if((col==a[i][j]||vis[i][j])&&(col==a[i+1][j+1]||vis[i+1][j+1])&&(col==a[i+1][j]||vis[i+1][j])&&(col==a[i][j+1]||vis[i][j+1])) return col;
        return 0;
    }
    inline void main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);cout.tie(0);
        cin>>n>>m;
        for(int i=1;i<=n;++i)
            for(int j=1;j<=m;++j) cin>>a[i][j];
        for(int i=1;i<n;++i)
        {
            for(int j=1;j<m;++j)
            {
                if(check(i,j)) q.push((node){i,j,a[i][j]});
            }
        }
        while(!q.empty())
        {
            int x=q.front().x,y=q.front().y;
            if(vis2[x][y]){q.pop(); continue;}
            st[++top]=q.front();
            q.pop();
            vis2[x][y]=1;
           // cout<<x<<' '<<y<<"!!"<<endl;
            vis[x][y]=vis[x+1][y]=vis[x][y+1]=vis[x+1][y+1]=1;
            int tmp;
            if((tmp=check(x-1,y))&&!vis2[x-1][y]) q.push((node){x-1,y,tmp});
            if((tmp=check(x+1,y))&&!vis2[x+1][y]) q.push((node){x+1,y,tmp});
            if((tmp=check(x,y-1))&&!vis2[x][y-1]) q.push((node){x,y-1,tmp});
            if((tmp=check(x,y+1))&&!vis2[x][y+1]) q.push((node){x,y+1,tmp});
            if((tmp=check(x+1,y+1))&&!vis2[x+1][y+1]) q.push((node){x+1,y+1,tmp});

        }
        bool flag=1;
        for(int i=1;i<n;++i)
        {
            for(int j=1;j<m;++j)
            {
                if(!vis[i][j]) flag=0; 
            }
        }
        if(!flag) cout<<"-1\n";
        else
        {
            cout<<top<<'\n';
            while(top)
            {
                cout<<st[top].x<<' '<<st[top].y<<' '<<st[top].z<<'\n';
                --top;
            }
        }
    }
}
signed main()
{
    red::main();
    return 0;   
}
/*

*/

E

题意：

给定数组\(A\)，初始时值都是\(0\)，颜色都是\(1\)

有以下操作：

\(1:\)把区间\([l,r]\)涂成颜色\(c\)

\(2:\)把所有颜色为\(c\)的格子加\(val\)

\(3:\)查询\(pos\)位置的值

解答：

肯定不能不连续的给区间加数，考虑线段树颜色均摊。用一个全局标记记录每个颜色的值的改变量，当改变某个位置上的颜色时，把这段区间先加上原来颜色的改变量，再减去当前颜色的改变量。这样两次赋值之间的颜色改变量就留在位置上了。

当查询一个颜色为\(c\)的点值时，返回\(ans[pos]+tag[c]\)。

#include<bits/stdc++.h>
using namespace std;
namespace red{
#define int long long
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define lowbit(i) ((i)&(-i))
#define mid ((l+r)>>1)
#define eps (1e-8)
    const int N=1e6+10,mod=1e9+7,inf=2e9;
    int n,m;
    string opt;
    int sum[N];
    struct segment_tree
    {
        int tag1[N<<2],tag2[N<<2];
        int col[N<<2];
        inline void build(int l,int r,int p)
        {
            col[p]=1;
            if(l==r) return;
            build(l,mid,ls(p));
            build(mid+1,r,rs(p));
        }
        inline void tag_union(int p,int c,int k)
        {
            tag1[p]+=k;
            if(c)col[p]=c,tag2[p]=c;
        }
        inline void pushdown(int p)
        {
            tag_union(ls(p),tag2[p],tag1[p]);
            tag_union(rs(p),tag2[p],tag1[p]);
            tag1[p]=tag2[p]=0;
        }
        inline void update(int tl,int tr,int l,int r,int p,int c)
        {
            if(col[p]&&tl<=l&&r<=tr)
            {
                tag_union(p,c,sum[col[p]]-sum[c]);
                return;
            }
            if(tag1[p]||tag2[p]) pushdown(p);
            if(tl<=mid) update(tl,tr,l,mid,ls(p),c);
            if(tr>mid) update(tl,tr,mid+1,r,rs(p),c);
            if(col[ls(p)]==col[rs(p)]) col[p]=col[ls(p)];
            else col[p]=0;
        }
        inline int query(int pos,int l,int r,int p)
        {
            if(l==r) return tag1[p]+sum[col[p]];
            if(tag1[p]||tag2[p]) pushdown(p);
            if(pos<=mid) return query(pos,l,mid,ls(p));
            return query(pos,mid+1,r,rs(p));
        }
    }T;
    inline void main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);cout.tie(0);
        cin>>n>>m;
        T.build(1,n,1);
        for(int i=1;i<=m;++i)
        {
            cin>>opt;
            if(opt[0]=='C')
            {
                int x,y,z;cin>>x>>y>>z;
                T.update(x,y,1,n,1,z);
            }
            if(opt[0]=='A')
            {
                int x,y;cin>>x>>y;
                sum[x]+=y;
            }
            if(opt[0]=='Q')
            {
                int x;cin>>x;
                cout<<T.query(x,1,n,1)<<'\n';
            }
        }
    }
}
signed main()
{
    red::main();
    return 0;   
}
/*

*/

F

题意：

给\(n\)个数字，进行至多两次操作：每次选择一段区间\([l,r]\)，然后把区间内的数字都减去\(x(x\leq min\{a_l,…a_r\})\)，获得贡献\(x*(r-l+1)\)，求最大贡献。

考虑两次区间的覆盖情况：相离，相交，覆盖。

相离：

很好做，两边分别做一个经典单调栈。

相交：

如果重复区间是\([l,r]\)，其中最小值是\(h\)，一条线往左扩展，另一条线往右扩展。

那么左边对某个位置\(i<l\)来说，它\([i,r]\)的最小值\(min_1\)决定了它的高度上限。而右边我们只能选择高度不超过\(h-min_1\)的部分。可以发现这部分可以用双指针实现。

右侧同理。

覆盖：

还是双指针，更好想。

就是他妈的难写，焯，还\(√ 8\)的卡常

#pragma GCC optimize(3)
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
namespace red{
#define int long long
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define lowbit(i) ((i)&(-i))
#define mid ((l+r)>>1)
#define eps (1e-8)
    const int N=1e4+10,mod=1e9+7,inf=2e9;
    int n,ans;
    int a[N];
    int pre[N],suf[N];
    int minn[N];
    int tmp[N];
    signed tl[N],tr[N],st[N],top;
    inline void work(int l,int r)
    {
        top=0;
        for(int i=l;i<=r;++i)
        {
            while(top&&a[st[top]]>a[i])
            {
                tr[st[top--]]=i;
            }
            st[++top]=i;
        }
        while(top) tr[st[top--]]=r+1;
        for(int i=r;i>=l;--i)
        {
            while(top&&a[st[top]]>a[i])
            {
                tl[st[top--]]=i;
            }
            st[++top]=i;
        }
        while(top) tl[st[top--]]=l-1;
    }
    inline void main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);cout.tie(0);
        cin>>n;
        for(int i=1;i<=n;++i) cin>>a[i];
        for(int i=1;i<=n;++i)
        {
            int minn=a[i];
            for(int j=i;j<=n;++j)
            {
                minn=min(minn,a[j]);
                pre[j+1]=max(pre[j+1],minn*(j-i+1));
                suf[i]=max(suf[i],minn*(j-i+1));
            }
        }
        for(int i=0;i<=n+1;++i)
        {
            for(int j=i;j<=n;++j)
            {
                ans=max(ans,pre[i]+suf[j]);
            }
        }
        work(1,n);
        for(int i=1;i<=n;++i)
        {
            int l=tl[i]+1,r=tr[i]-1;
            minn[l]=a[l];
            for(int j=l+1;j<=n;++j) minn[j]=min(minn[j-1],a[j]);
            for(int j=n;j>r;--j) tmp[j]=max(minn[j]*(j-l+1),tmp[j+1]);
            minn[r]=a[r];
            for(int j=r-1;j>=1;--j) minn[j]=min(minn[j+1],a[j]);
            for(int j=1;j<l;++j) tmp[j]=max(minn[j]*(r-j+1),tmp[j-1]);
            int t1=n,qaq=a[i];
            int t2=r;
            minn[l]=a[l];
            for(int j=l+1;j<=n;++j) minn[j]=min(minn[j-1],a[j]);
            for(int j=l-1;j>=1;--j)
            {
                if(a[j]<qaq) qaq=a[j];
                while(t1>r&&minn[t1]+qaq<a[i]) --t1;
                ans=max(ans,qaq*(r-j+1)+tmp[t1+1]);
                ans=max(ans,qaq*(r-j+1)+(a[i]-qaq)*(t1-l+1));
                while(t2<n&&a[t2+1]>=qaq) ++t2;
                ans=max(ans,qaq*(l-j+t2-r)+a[i]*(r-l+1));
            }

            minn[r]=a[r];
            for(int j=r-1;j>=1;--j) minn[j]=min(minn[j+1],a[j]);
            t1=1,t2=l,qaq=a[i];
            for(int j=r+1;j<=n;++j)
            {
                if(a[j]<qaq) qaq=a[j];
                while(t1<l&&minn[t1]+qaq<a[i]) ++t1;
                ans=max(ans,qaq*(j-l+1)+tmp[t1-1]);
                ans=max(ans,qaq*(j-l+1)+(a[i]-qaq)*(r-t1+1));
                while(t2>1&&a[t2-1]>=qaq) --t2;
                ans=max(ans,qaq*(j-r+l-t2)+a[i]*(r-l+1));
            }
        }
        cout<<ans<<'\n';
    }
}
signed main()
{
    red::main();
    return 0;   
}
/*

*/