CF558E A Simple Task
难度：2300
一个字符串，长度为n，m次操作，每次操作规定对于l到r升序或者降序，输出最终操作完的字符串
线段树
用26棵线段树维护数组中的每一个字母，当规定升序时，我们把对于26个线段树在这段区间内从新进行填补，首先找到这段区间内a的个数，然后把a平铺上，在找到b的个数，把b平铺上，相当于把原本字符串中所有相同的字母拆分成26条平行的线段树，在对应区间内，如果升序就从a到z重新平铺字母，如果降序就从z到a重新平铺字母
#include <bits/stdc++.h>
#define ls p<<1
#define rs p<<1|1
#define mid (l+r)/2
//#define int long long
#define fastio ios::sync_with_stdio(0);cout.tie(0);cin.tie(0);
const int N = 1e5+100;
using namespace std;
char s[N];
int tree[27][N<<2],tag[27][N<<2];
void up(int p,int rt)
{
tree[rt][p]=tree[rt][ls]+tree[rt][rs];
}
void bulid(int l,int r,int p)
{
if(l==r)
{
tree[s[l]-'a'+1][p]=1;
return ;
}
bulid(l,mid,ls);
bulid(mid+1,r,rs);
for(int i=1;i<=26;i++)
up(p,i);
}
void down(int l,int r,int p,int rt)
{
if(tag[rt][p]!=-1)
{
tag[rt][ls]=tag[rt][p];
tag[rt][rs]=tag[rt][p];
tree[rt][ls]=tag[rt][p]*(mid-l+1);
tree[rt][rs]=tag[rt][p]*(r-mid);
tag[rt][p]=-1;
}
}
void fix(int l,int r,int p,int nl,int nr,int rt,int k)
{
if(l>=nl&&r<=nr)
{
tree[rt][p]=(r-l+1)*k;
tag[rt][p]=k;
return ;
}
down(l,r,p,rt);
if(mid>=nl)
{
fix(l,mid,ls,nl,nr,rt,k);
}
if(mid<nr)
{
fix(mid+1,r,rs,nl,nr,rt,k);
}
up(p,rt);
}
int query(int l,int r,int p,int nl,int nr,int rt)
{
if(l>=nl&&r<=nr)
{
return tree[rt][p];
}
down(l,r,p,rt);
int res=0;
if(mid>=nl)
{
res+=query(l,mid,ls,nl,nr,rt);
}
if(mid<nr)
{
res+=query(mid+1,r,rs,nl,nr,rt);
}
return res;
}
void out(int l,int r,int p)
{
if(l==r)
{
for(int i=1;i<=26;i++)
{
if(tree[i][p])
{
s[l]='a'+i-1;
break;//?
}
}
return ;
}
for(int i=1;i<=26;i++)
{
down(l,r,p,i);
}
out(l,mid,ls);
out(mid+1,r,rs);
}
signed main()
{
int n,m,l,r,c;
for(int i=1;i<=26;i++)
memset(tag[i],-1,sizeof(tag[i]));
cin>>n>>m>>(s+1);
bulid(1,n,1);
for(int i=1;i<=m;i++)
{
cin>>l>>r>>c;
int temp;
if(c)
{
temp=l-1;
for(int i=1;i<=26;i++)
{
int num=query(1,n,1,l,r,i);
if(num==0)
continue;
fix(1,n,1,l,r,i,0);
fix(1,n,1,temp+1,temp+num,i,1);
temp+=num;
}
}
else
{
temp=l-1;
for(int i=26;i>=1;i--)
{
int num=query(1,n,1,l,r,i);
if(num==0)
continue;
fix(1,n,1,l,r,i,0);
fix(1,n,1,temp+1,temp+num,i,1);
temp+=num;
}
}
}
out(1,n,1);
for(int i=1;i<=n;i++)
cout<<s[i];
return 0;
}
这题可以说每一招都打在我的数学薄弱环节了
1.费马最小定理求逆元
2.（a/b）%k=a%k*inv(b)%k
3.杨辉三角
哈哈，没想到这个小题目包含这么多东西
费马最小定理求逆元
ll get_inv(ll x)
{
return pw(x,mod-2)%mod;
}
求组合
ll C(ll x,ll y)
{
return jc[x]*get_inv(jc[x-y])%mod*get_inv(jc[y])%mod;
}
for(int i=1;i<N;i++)
{
jc[i]=jc[i-1]*i%mod;
}
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N =4e5+10;
const int mod=1e9+7;
int n,m,q;
int jc[N];
int pw(int x,int y)
{
int res=1ll;
while(y)
{
if(y&1ll)
res=res*x%mod;
x=x*x%mod;
y>>=1ll;
}
return res%mod;
}
int get_inv(int x)
{
return pw(x,mod-2ll)%mod;
}
int C(int x,int y)
{
return jc[x]*get_inv(jc[x-y])%mod*get_inv(jc[y])%mod;
}
signed main()
{
cin>>n>>m>>q;
jc[0]=1;
for(int i=1;i<N;i++)
{
jc[i]=jc[i-1]*i%mod;
}
int num=pw(2ll,n+m),ans;
while(q--)
{
int a,b;
cin>>a>>b;
if(a==n)
{
ans=num*C((int)a+b-1,(int)a-1)%mod*get_inv(pw((int)2,(int)a+b))%mod;
}
else if(b==m)
{
ans=num*C((int)a+b-1,(int)b-1)%mod*get_inv(pw((int)2,(int)a+b))%mod;
}
cout<<ans<<endl;
}
return 0;
}
