昨晚玩游戏竟然不小心错过了CF。。我是有多浪啊。 今天总算趁着下课时间补了,感觉最后两题还是挺有意思的,写个题解。
D:
题目大意：
给出一个括号序列,问有多少个子序列 是k个'(' + k个')' 这样的形式。 n<=200000
解法：
对于每个'('的位置,计算以它为最右边的'('的合法子序列数。 假设它左边(包括它)有$l$个'(', 右边有 $r$个')' , 如果子序列的长度2k, 那么
方案数有$\binom{l-1}{k-1} * \binom{r}{k}= \binom{l-1}{l-k} * \binom{r}{k}$
这个式子对$k$求和是 $\binom{l+r-1}{l}$ 可以预处理阶乘O(1)计算出。
代码：
#include <iostream>
#include <string>
#include <cstring>
#include <map>
#include <cmath>
#include <set>
#include <bitset>
using namespace std; typedef long long ll;
typedef pair<int,int> pii; #define N 400010
#define X first
#define Y second const int INF=<<;
const int Mod=;
int ans;
char s[N];
int fac[N],fac_inv[N]; int Power(int x,int p)
{
int res=;
for (;p;p>>=)
{
if (p&) res=1ll*res*x%Mod;
x=1ll*x*x%Mod;
}
return res;
} int C(int n,int m)
{
if (m==) return ;
if (n==) return ;
int res=1ll*fac[n]*fac_inv[m]%Mod;
return 1ll*res*fac_inv[n-m]%Mod;
} int l[N],r[N]; int main()
{
//freopen("in.in","r",stdin);
//freopen("out.out","w",stdout); fac[]=fac_inv[]=;
for (int i=;i<N;i++)
{
fac[i]=1ll*fac[i-]*i%Mod;
fac_inv[i]=Power(fac[i],Mod-);
}
int n; scanf("%s",s+);
n=strlen(s+); for (int i=;i<=n;i++) l[i]=l[i-]+(s[i]=='(');
for (int i=n;i>=;i--) r[i]=r[i+]+(s[i]==')'); for (int i=;i<=n;i++)
{
if (s[i]!='(') continue;
if (!r[i]) continue;
ans+=C(l[i]+r[i]-,l[i]);
if (ans>=Mod) ans-=Mod;
} printf("%d\n",ans);
return ;
}
E：
题目大意：
一开始有一个1-n的排列,然后每次操作交换两个数,每次询问逆序对数。 n<=200000,Q<=50000
解法：
假设我们交换了a[l],a[r], 那么逆序对数如何改变呢？
首先逆序对数会减少[l+1,r-1]这个区间里 比a[r]大的数 和 比a[l]小的数。
然后会增加[l+1,r-1]这个区间里 比a[r]小的数 和 比a[l]大的数。
因此我们需要快速计算某个区间里有多少个数比x大的。
我的做法是分块,每个块维护一个树状数组即可。 复杂度比较悬,换了几次块的大小,极限数据本地跑要10s,但是CF机子2s就跑完了？
代码：
By lzw4896s, contest: Codeforces Round # (Div. ), problem: (E) Anton and Permutation, Accepted, #
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <map>
#include <set>
#include <cmath> using namespace std; typedef long long ll;
#define N 200010 int n,m,block;
int v[N],id[N]; inline int Lowbit(int x){return x&-x;} struct BIT
{
int c[N];
void Insert(int x,int v)
{
while (x<=n)
{
c[x]+=v;
x+=Lowbit(x);
}
}
int Sum(int l,int r)
{
if (l>r) return ;
int res=,x=r;
while (x)
{
res+=c[x];
x-=Lowbit(x);
}
x=l-;
while (x)
{
res-=c[x];
x-=Lowbit(x);
}
return res;
}
}tree[]; int Query(int l,int r,int low,int high)
{
int res=;
if (id[r]-id[l]<=)
{
for (int i=l;i<=r;i++) res+=(v[i]>=low && v[i]<=high);
return res;
}
for (int i=l;i<=block*id[l];i++) res+=(v[i]>=low && v[i]<=high);
for (int i=block*(id[r]-)+;i<=r;i++) res+=(v[i]>=low && v[i]<=high);
for (int i=id[l]+;i<=id[r]-;i++) res+=tree[i].Sum(low,high);
return res;
} int main()
{
///freopen("in.in","r",stdin);
//freopen("out.out","w",stdout); int Q,l,r; ll ans=;
scanf("%d%d",&n,&Q);
if (n>) block=;
else block=;
for (int i=;i<=n;i++) v[i]=i;
//block=4; for (int i=;i<=n;i+=block)
{
int j=min(n,i+block-); m++;
for (int k=i;k<=j;k++)
{
id[k]=m;
tree[m].Insert(k,);
}
}
while (Q--)
{
scanf("%d%d",&l,&r);
if (l==r)
{
printf("%I64d\n",ans);
continue;
}
if (l>r) swap(l,r);
if (v[l]>v[r]) ans--;
else ans++;
tree[id[l]].Insert(v[l],-);
tree[id[r]].Insert(v[r],-);
if (r-l>)
{
ans-=Query(l+,r-,v[r]+,n);
ans-=Query(l+,r-,,v[l]-);
ans+=Query(l+,r-,,v[r]-);
ans+=Query(l+,r-,v[l]+,n);
}
swap(v[l],v[r]);
tree[id[l]].Insert(v[l],);
tree[id[r]].Insert(v[r],);
//cout<<"eee\n";
printf("%I64d\n",ans);
//for (int i=1;i<=n;i++) cout<<v[i]<<" ";
//cout<<endl;
/*for (int i=1;i<=m;i++)
{
for (int j=1;j<=n;j++) cout<<tree[i].Sum(j,j)<<" ";
cout<<endl;
}*/
} return ;
}