A.普通计算姬

题意：给丁一棵树，每个点有一个权值，用sum(x)表示以x为根的子树的权值和，要求支持两种操作：

1 u v  ：修改点u的权值为v。

2 l  r   :  求∑sum[i] l<=i<=r

n,m(操作数)<=10^5

题解:数据范围比较小，考虑分块重建的做法。

求出每个点的dfs序和子树的区间，这样就可以On建出所有节点的sum的前缀和。

然后每次修改操作都把操作存下来，每次查询先找出这段区间的和，再去操作里处理这些操作对这个查询的影响。

具体实现就是：把每个点的子树的dfs序范围的左右端点都扔到一棵主席树里面，每次查询一个区间时候，枚举修改操作，在主席树里面查询，修改操作修改的点影响的子树数量就=右端点大等于它的dfs序的数量-左端点大于它的dfs序的数量。

然后当操作达到一定数量的时候，暴力On重建一发。

如果操作达到k时候重建，那么复杂度就大概是n^2/k+nklogn,题目有4s，很科学。

然后这破题写了好久，还wa了好多次,代码丑。

#include
     
      #include
      
       #include
       
        #define ll unsigned long longusing namespace std;inline int read(){   int  x=0,f=1;char ch=getchar();   while(ch<'0'||ch>'9'){
   if(ch=='-') f=-1;ch=getchar();}   while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}   return x*f;} long long q[100005],q2[100005];int top=0;long long b[100005];ll sum[100005],num[100005];int rt1[100005],rt2[100005];int op,u,v,cnt=0,n,m,dn=0,cc=0,rt,head[100005];struct edge{    int to,next;}e[200005];int nl[100005],nr[100005];ll ans=0; struct TREE{    int l,r,x;}T[10000005]; void ins(int f,int t){    e[++cnt].next=head[f];head[f]=cnt;    e[cnt].to=t;} int query(int x,int ad){//  cout<<"query"<
        
         <<" "<
         
          <
          
           n||x==0) return 0; int l=1,r=n,sum=0; while(l
           
            >1; if(ad<=mid) {sum+=T[T[x].r].x;x=T[x].l;r=mid;} else {x=T[x].r;l=mid+1;} } //cout<
            
             <<" "<
             
              <
              
               >1; if(ad<=mid) { T[x].l=++cc;T[x].r=T[ls].r;T[x].x=T[ls].x+1; r=mid;x=T[x].l;ls=T[ls].l; } else { T[x].r=++cc;T[x].l=T[ls].l;T[x].x=T[ls].x+1; l=mid+1;x=T[x].r;ls=T[ls].r; }// cout<
               
                <<" "<
                
                 <<" "<
                 
                  <<" "<
                  
                   <
                   
                    =50) rebuild(); } return 0;}
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     

B.文艺计算姬

题意：求一个一边有n个点，另一边有m个点的完全二分图的生成树数量%p     n,m,p<=10^18

题解：观察之后发现：答案是n^(m-1)*m^(n-1) 由于n,m非常大，所以手写一个大整数乘法就行了。

顺便一说，ditoly 0ms+代码短卡到rank1了，真的劲。复杂度（log^2n)

#include
     
      #include
      
       #define ll unsigned long longusing namespace std;inline ll read(){    ll x=0,f=1;char ch=getchar();    while(ch<'0'||ch>'9'){
   if(ch=='-') f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}    return x*f;} ll n,m,p; ll mul(ll a,ll b,ll mod){    ll sum=0;    for(;b;b>>=1,a=(a<<1)%mod)if(b&1)sum=(sum+a)%mod;    return sum;} ll pow(ll x,ll p,ll mod){    ll sum=1;    for(ll i=x;p;p>>=1,i=mul(i,i,mod))        if(p&1) sum=mul(sum,i,mod);    return sum;} int main(){    n=read();m=read();p=read();    ll ans=mul(pow(n,m-1,p),pow(m,n-1,p),p);    cout<
      
     

 

C.有一个点位于(0,0)，你要把它移到(ex,ey)，有两种可用的移动，如果原来位于(x,y)的话分别可以让他移动到(x+a,y+b)和(x+c,y+d)a*d-b*c!=0

还有n个点是限制点，不能走，求移动的方案数。  n<=500,限制点的坐标绝对值<=500

题解： 考虑dp+容斥原理，预处理（解方程+组合数）出每两个点之间的方案数量，答案=方案数-走一个限制点的方案数+走两个限制点的方案-........

但这显然要求转移是有序的，我们发现题目只有两种可用的移动，所以我们可以考虑以其中一个向量为x轴，然后按照y坐标为第一关键字，x坐标为第二关键字乱排序一下（可以利用向量的点积和叉积），然后直接dp就没啦。

复杂度(nlogn+n^2)

#include
     
      #include
      
       #include
       
        #define ll long long#define mod 1000000007using namespace std;inline int read(){    int x=0,f=1;char ch=getchar();    while(ch<'0'||ch>'9'){
   if(ch=='-') f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}    return x*f;}  ll q[500005],r[500005];ll f[1005];ll g[1005][1005];double xie;int a,b,c,d;int ex,ey,n;struct node{    int x,y,nx,ny;}s[1005]; bool cmp1(node xx,node yy){
   return xx.nx
        
         
          yy.nx||(xx.nx==yy.nx&&xx.ny