好久没打CF了，打场div2练手。因为比较晚还没提前睡有点神志不清，E题打了莫名其妙的代码调了好久，最后结束后5分钟才发现哪里错了……
AC:ABCD Rank:60
A.Anton and Polyhedrons
题目大意：五种多面体，每种用一个英文单词表示，某人有n个多面体，分别告诉你这n个多面体是什么，求总共多少个面。（n<=200,000）
思路：普及培训，选择结构+循环结构。
#include<cstdio>
int main()
{
int n,ans=;char s[];
scanf("%d",&n);
while(n--)
{
scanf("%s",s);
if(s[]=='T')ans+=;
if(s[]=='C')ans+=;
if(s[]=='O')ans+=;
if(s[]=='D')ans+=;
if(s[]=='I')ans+=;
}
printf("%d",ans);
}
B.Anton and Classes
题目大意：给你n+m条数轴上的线段，要求从前n个中选出一条，后m个中选出一条，使得这两条距离最大，求出这个距离。（n,m<=200,000）
思路：分别对两部分线段找出最右的左端点和最左的右端点，再分情况计算一下答案，复杂度O(n+m)。
#include<cstdio>
#include<algorithm>
using namespace std;
char B[<<],*S=B,C;int X;
inline int read()
{
while((C=*S++)<''||C>'');
for(X=C-'';(C=*S++)>=''&&C<='';)X=(X<<)+(X<<)+C-'';
return X;
}
#define INF 0x7FFFFFFF
int main()
{
fread(B,,<<,stdin);
int n,x0=,y0=INF,x1=,y1=INF;
for(n=read();n--;)x0=max(x0,read()),y0=min(y0,read());
for(n=read();n--;)x1=max(x1,read()),y1=min(y1,read());
printf("%d",max(,max(x1-y0,x0-y1)));
}
C.Anton and Fairy Tale
题目大意：谷仓一开始装满n个稻子，第i天会先少掉i个稻子后补充至多m个稻子（补充后总量不超过n），问什么时候第一次没稻子。（n,m<=10^18）
思路：相当于n-m个稻子，前m天不会少稻子，第i+m天会少i个稻子，二分答案算一算最可以了，注意特判n<m，复杂度O(logn)。
#include<iostream>
using namespace std;
int main()
{
long long n,m,l,r,mid,ans;
cin>>n>>m;
if(m>n)return cout<<n,;
for(l=,r=;l<=r;)
{
mid=l+r>>;
if(mid*(mid+)>>>=n-m)ans=mid,r=mid-;
else l=mid+;
}
cout<<ans+m;
}
D.Anton and School - 2
题目大意：给出一个长为n的由左右括号组成的字符串，问有多少个子序列满足长为k，k为偶数，前k/2个是左括号，后k/2个是右括号。（n<=200,000）
思路：枚举子序列的最后一个左括号，求出他前面有多少左括号，后面有多少右括号，统计答案，观察发现若前面有l个左括号，后面有r个右括号，则对答案的贡献为C(l+r,r-1)，复杂度O(n)。
#include<cstdio>
#define MN 200000
#define MOD 1000000007
char s[MN+];
int f[MN+],v[MN+];
inline int inv(int x)
{
int r=,y=MOD-;
for(;y;y>>=,x=1LL*x*x%MOD)if(y&)r=1LL*r*x%MOD;
return r;
}
int main()
{
int i,l,r,ans=;
scanf("%s",s);
for(i=f[]=;i<=MN;++i)f[i]=1LL*f[i-]*i%MOD;
for(v[i=MN]=inv(f[MN]);i--;)v[i]=1LL*v[i+]*(i+)%MOD;
for(i=l=r=;s[i];++i)if(s[i]==')')++r;
for(i=;r;++i)s[i]=='('?(ans=(ans+1LL*f[l+r]*v[l+]%MOD*v[r-])%MOD,++l):--r;
printf("%d",ans);
}
E.Anton and Permutation
题目大意：一个长度为n的排列一开始为1,2,3,…,n，q次操作，每次交换其中两个元素，求每次操作后排序的逆序对数。（n<=200,000，q<=50,000）
思路：容易想到用数据结构维护这个序列，交换x和y时，我们查询x和y之间有多少个小于x的和小于y的，直接计算答案即可，用树状数组套权值线段树会爆内存，所以我写了树状数组套Treap，复杂度O(nlogn^2)。本来cf上的这种题应该不是这么暴力的，但看到q只有50000时限又开得很大，还是乖乖打数据结构……人菜一直挂，发现一个函数忘记return……已经好几次遇到这种事了，下次打函数先打return。
#include<cstdio>
#include<algorithm>
using namespace std;
char B[<<],*S=B,C;int X;
inline int read()
{
while((C=*S++)<''||C>'');
for(X=C-'';(C=*S++)>=''&&C<='';)X=(X<<)+(X<<)+C-'';
return X;
}
#define MN 200000
#define ND 6000000
#define L(x) c[x][0]
#define R(x) c[x][1]
int fa[ND+],c[ND+][],s[ND+],z[ND+],p[ND+];
int t[MN+],tn=MN;
inline int ran()
{
static int x=;
return x^=x<<,x^=x>>,x^=x<<;
}
inline void up(int x){s[x]=s[L(x)]+s[R(x)]+;}
void rotate(int x)
{
int f=fa[x],ff=fa[f],l=R(f)==x,r=l^;
fa[f]=x;fa[x]=ff;fa[c[x][r]]=f;
c[ff][R(ff)==f]=x;c[f][l]=c[x][r];c[x][r]=f;
up(f);up(x);
}
void ins(int f,int t,int x)
{
while(c[f][t])t=x>z[f=c[f][t]],++s[f];
fa[c[f][t]=++tn]=f;p[tn]=ran();z[tn]=x;s[tn]=;
for(;fa[tn]>MN&&p[tn]>p[fa[tn]];)rotate(tn);
}
int find(int x,int k)
{
while(z[x]!=k)x=k<z[x]?L(x):R(x);
return x;
}
void del(int x)
{
while(L(x)||R(x))rotate(p[L(x)]>p[R(x)]?L(x):R(x));
c[fa[x]][R(fa[x])==x]=;
while(x=fa[x])up(x);
}
int get(int x,int t)
{
return x?z[x]>t?get(L(x),t):s[L(x)]++get(R(x),t):;
}
void ins(int x,int z){for(;x<=MN;x+=x&-x)ins(x,,z);}
void del(int x,int z){for(;x<=MN;x+=x&-x)del(find(L(x),z));}
int sum(int x,int z){int r=;for(;x;x-=x&-x)r+=get(L(x),z);return r;}
int main()
{
fread(B,,<<,stdin);
int n,m,i,x,y;long long ans=;
n=read();m=read();p[]=0x80000000;
for(i=;i<=n;++i)t[i]=i,ins(i,i);
while(m--)
{
x=read();y=read();if(x>y)swap(x,y);
if(x<y)
{
ans+=((sum(y-,t[y])-sum(x,t[y])-sum(y,t[x])+sum(x,t[x]))<<)+;
del(x,t[x]);del(y,t[y]);
swap(t[x],t[y]);
ins(x,t[x]);ins(y,t[y]);
}
printf("%I64d\n",ans);
}
}