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;
}
/*
*/