来自FallDream的博客。未经允许，请勿转载，谢谢。

----------------------------------------------------

A.积分，不会  以后补

B.给定一个n*m的矩阵，每个点是0或者1，然后q个操作，每次把一个位置取反，然后询问最大的全是1的正方形的边长。n*m<=4000000 , q<=3900

题解：我们用一个线段树把所有行维护起来，然后每一行对每一列维护这个行区间的这一列的u和d，u表示从最下面一个最多有多少个连续的1，d表示从上面网下面最多有多少个连续的1，这两个参数是很好合并的。然后我们考虑计算过中线的答案。我们用两个指针ij,再用两个单调队列，维护u和d单调下降。每当 i - j + 1> u[tail] + d[tail] 的时候，我们把j指针往前移。最后我们用i - j + 1更新答案。

复杂度qmlogn  如果n<m我们把nm交换一下。

最近被奇怪的代码风格洗脑了，写了一个不像是我写的程序（听我解释，我真的不是抄的.....) 其实我真正的代码风格像C题那样就是一团垃圾

#include
     
      #include
      
       #define MN 2000#define TESTusing 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;}inline int cread(){    char ch = getchar();    while(ch != '.' && ch != 'X') ch = getchar();    return ch == '.' ? 1 : 0;}int n , m , q , qx[MN + 5] , ltop , qy[MN + 5] , rtop , ltail , rtail;bool *s[MN + 5] , rev;struct Segment_Tree{    int ans , w;    int *u , *d;    Segment_Tree *l , *r;    void init(int x)    {        ans = 0;        for(int i = 1 ; i <= n ; ++i)            u[i] = d[i] = s[i][x] , ans |= s[i][x];     }        void update()    {        ans = max ( l->ans , r->ans );                int x , k = 1;        for(int i = 1 ; i <= n ; ++i)        {            u[i] = l -> d[i];                d[i] = r -> u[i];         }                                        qx[ltop = 1] = qy[rtop = 1] = 1;        ltail = rtail = 1;                for ( int i = 2; i <= n ; ++i)        {            while(u[i] <= u[qx[ltop]] && ltop >= ltail) ltop --;            while(d[i] <= d[qy[rtop]] && rtop >= rtail) rtop --;                        qx[++ ltop] = i;             qy[++ rtop] = i;             while(i - k + 1> u[qx[ltail]] + d[qy[rtail]] && i > k)             {                ++ k;                if(qx[ltail] < k) ltail ++;                 if(qy[rtail] < k) rtail ++;            }            ans = max(ans , i - k + 1);        }                for(int i = 1 ; i <= n ; ++i)        {            u[i] = ( l -> u[i] == l -> w) ? r -> u[i] + l -> w : l -> u[i];                d[i] = ( r -> d[i] == r -> w) ? l -> d[i] + r -> w : r -> d[i];         }        }        void modify(int x , int lt = 1 , int rt = m)    {        if(lt == rt) { init(x); return;}        int mid = lt + rt >> 1;        if(x <= mid) l -> modify(x , lt , mid);        else  r -> modify(x , mid + 1, rt);        update();    }        Segment_Tree(int  lt , int rt )    {        u = new int [n + 2];        d = new int [n + 2];        w = rt - lt + 1;        if(lt == rt) { init(lt); return;}        int mid = lt + rt >> 1;        l = new Segment_Tree(lt , mid);        r = new Segment_Tree(mid + 1 , rt);        update();     }    }*rt;int main(){#ifdef TEST    freopen("s.in" , "r" , stdin);    freopen("s.out" , "w" , stdout);#endif    n = read(); m = read(); q = read();    if( n > m) swap(n , m),rev = true;     for(int i = 1; i <= n ; ++i)        s[i] = new bool [m + 2];         if(!rev)        for(int i = 1; i <= n ; ++i)            for(int j = 1; j <= m ; ++j)                s[i][j] = cread();    else         for(int i = 1; i <= m ; ++i)            for(int j = 1; j<= n ; ++j)                s[j][i] = cread();                    rt = new Segment_Tree(1 , m);    for(int i = 1; i <= q ; ++i)    {        int x = read() , y = read();        if(rev) swap(x , y);        s[x][y] ^= 1;        rt -> modify(y);        printf("%d\n" , rt -> ans);    }            return 0;}
      
     

 

C.给定一棵n个点树，每个点可以涂成白的或者黑的。给定b条链和b个权值bi，表示这条链上的点全是黑色时候能得到bi的贡献。还有a条链和a个权值，表示全部涂成白色能得到的贡献。你要求出最大贡献。n<=100000  a,b<=30000  3s

题解：神题

最小割，很显然黑白链就是一个二分图。但是直接建图是不行的，所以我们考虑优化一下，把树拿去树剖一下，然后建两棵线段树，一棵只能往下走，一棵只能往上走。每条链对两棵线段树上的对应的log个区间建边，最后跑一次最小割。复杂度很玄学，就算O(能过)吧。

ditoly真的强，居然在现场想出了这个做法...%%%

#include
     
      #include
      
       #include
       
        using namespace std;#define N 800000#define MAXL 10000000#define MV 860000#define MAXN 100000#define MN 100000#define S 0#define tt 860001#define INF 2000000000inline 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;}int dn=0,cnt=0,ans=0,n,B,W,head2[MAXN+5],head[MV+5],top[MAXN+5],qx[MV+5],qtop,tail;int dfn[MAXN+5],mx[MAXN+5],size[MAXN+5],dep[MAXN+5],fa[MAXN+5],q[MV+5],tp[MV+5];struct edge{    int to,next,w;}e[MAXL*2+5];struct edge2{    int to,next;}e2[MAXN*2+5];struct TREE{    int l,r;}T[MN*4+5];inline void ins(int f,int t){e2[++cnt].next=head2[f];head2[f]=cnt;e2[cnt].to=t;}inline void ins(int f,int t,int w){e[++cnt].next=head[f];head[f]=cnt;e[cnt].to=t;e[cnt].w=w;}inline void insw(int f,int t,int w){ins(f,t,w);ins(t,f,0);}void dfs(int x,int f){    size[x]=1;mx[x]=0;fa[x]=f;int maxn=0;    for(int i=head2[x];i;i=e2[i].next)if(e2[i].to!=f)    {        dep[e2[i].to]=dep[x]+1;dfs(e2[i].to,x);        size[x]+=size[e2[i].to];        if(size[e2[i].to]>maxn){maxn=size[e2[i].to];mx[x]=e2[i].to;}    }}void dfs2(int x,int t){    top[x]=t;dfn[x]=++dn;    if(mx[x])dfs2(mx[x],t);    for(int i=head2[x];i;i=e2[i].next)if(!dfn[e2[i].to])    {dfs2(e2[i].to,e2[i].to);}}void build(int x,int l,int r){    T[x].l=l;T[x].r=r;if(l==r)return;    int mid=(l+r)>>1;    insw(x,x<<1,INF);insw(x,x<<1|1,INF);    insw((x<<1)+4*MN,x+4*MN,INF);insw((x<<1|1)+4*MN,x+4*MN,INF);    build(x<<1,l,mid);build(x<<1|1,mid+1,r);}void insert(int from,int x,int l,int r){ //   cout<<"insert"<
        
         <<" "<
         
          <<" "<
          
           <<" "<
           
            <<" "<
            
             <<" "<<
             
              >1; if(r<=mid)insert(from,x<<1,l,r); else if(l>mid)insert(from,x<<1|1,l,r); else {insert(from,x<<1,l,mid);insert(from,x<<1|1,mid+1,r);}}void insert2(int to,int x,int l,int r){ // cout<<"insert2"<
              
               <<" "<
               
                <<" "<
                
                 <<" "<
                 
                  <<" "<
                  
                   <<" "<<
                   
                    >1; if(r<=mid)insert2(to,x<<1,l,r); else if(l>mid)insert2(to,x<<1|1,l,r); else {insert2(to,x<<1,l,mid);insert2(to,x<<1|1,mid+1,r);}}bool bfs(){ memset(q,0,sizeof(q));int i,j; for(q[qx[qtop=i=0]=S]=1;i<=qtop;i++) for(int j=tp[qx[i]]=head[qx[i]];j;j=e[j].next)if(!q[e[j].to]&&e[j].w) q[qx[++qtop]=e[j].to]=q[qx[i]]+1; return q[tt]>0;}int solve(int x,int f){ // cout<<"solve"<
                    
                     <<" "<
                     
                      <
                      
                       dep[top[v]]) {insert(N+i,1,dfn[top[u]],dfn[u]);u=fa[top[u]];} else {insert(N+i,1,dfn[top[v]],dfn[v]);v=fa[top[v]];} } if(dfn[u]>dfn[v])swap(u,v);insert(N+i,1,dfn[u],dfn[v]); } for(int i=1;i<=W;++i) { int u=read(),v=read(),x=read();insw(N+i+B,tt,x);ans+=x; while(top[u]!=top[v]) { // cout<
                       <<" "<
                        
                         <<" "<
                         
                          <<" "<
                          
                           <
                           
                            dep[top[v]]) {insert2(N+i+B,1,dfn[top[u]],dfn[u]);u=fa[top[u]];} else {insert2(N+i+B,1,dfn[top[v]],dfn[v]);v=fa[top[v]];} } if(dfn[u]>dfn[v])swap(u,v);insert2(N+i+B,1,dfn[u],dfn[v]); } while(bfs())ans-=solve(S,INF); printf("%d\n",ans); return 0;}