[size=45]难度评级低了吧Orz[/size]

3000分留念
虽然是水了一道做过的题qwq

Tarjan大法好！

[size=200]啊[/size]

《论鬼畜写法的危害》

《论鬼畜写法的危害》

思想奇^妙

这里是非常傻的出题人。。这是我東方模拟赛6中的一道很有意思的题，欢迎大家AC。

树状数组第一题mark

求大佬看一下为什么这个代码过不去这道题，W了三个点啊！！！

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cstring>

using namespace std;

struct node

{

 int data,rev,sum;

 node *son[2],*pre;

 bool judge();

 bool isroot();

 void pushdown();

 void update();

 void setson(node *child,int lr);

}lct[233];

int top,a,b;

node *getnew(int x)

{

 node *now=lct+ ++top;

 now->data=x;

 now->pre=now->son[1]=now->son[0]=lct;

 now->sum=0;

 now->rev=0;

 return now;

}

bool node::judge(){return pre->son[1]==this;}

bool node::isroot()

{

 if(pre==lct)return true;

 return !(pre->son[1]==this||pre->son[0]==this);

}

void node::pushdown()

{

 if(this==lct||!rev)return;

 swap(son[0],son[1]);

 son[0]->rev^=1;

 son[1]->rev^=1;

 rev=0;

}

void node::update(){sum=son[1]->sum+son[0]->sum+data;}

void node::setson(node *child,int lr)

{

 this->pushdown();

 child->pre=this;

 son[lr]=child;

 this->update();

}

void rotate(node *now)

{

 node *father=now->pre,*grandfa=father->pre;

 if(!father->isroot()) grandfa->pushdown();

 father->pushdown();now->pushdown();

 int lr=now->judge();

 father->setson(now->son[lr^1],lr);

 if(father->isroot()) now->pre=grandfa;

 else grandfa->setson(now,father->judge());

 now->setson(father,lr^1);

 father->update();now->update();

 if(grandfa!=lct) grandfa->update();

}

void splay(node *now)

{

 if(now->isroot())return;

 for(;!now->isroot();rotate(now))

 if(!now->pre->isroot())

 now->judge()==now->pre->judge()?rotate(now->pre):rotate(now);

}

node *access(node *now)

{

 node *last=lct;

 for(;now!=lct;last=now,now=now->pre)

 {

 splay(now);

 now->setson(last,1);

 }

 return last;

}

void changeroot(node *now)

{

 access(now)->rev^=1;

 splay(now);

}

void connect(node *x,node *y)

{

 changeroot(x);

 x->pre=y;

 access(x);

}

void cut(node *x,node *y)

{

 changeroot(x);

 access(y);

 splay(x);

 x->pushdown();

 x->son[1]=y->pre=lct;

 x->update();

}

int query(node *x,node *y)

{

 changeroot(x);

 node *now=access(y);

 return now->sum;

}

int main()

{

 freopen("aplusb.in","r",stdin);

 freopen("aplusb.out","w",stdout);

 scanf("%d%d",&a,&b);

 node *A=getnew(a);

 node *B=getnew(b);

 //连边 Link

 connect(A,B);

 //断边 Cut

 cut(A,B);

 //再连边 Again

 connect(A,B);

 printf("%d\n",query(A,B));

 return 0;

}

第一次榜上留名～～～

stl是个好东西

对着数据扩展我的词典= =
这tm与打表何异= =

各种W。
误以为一定要移走m块。

数据范围水……并没有写单调队列qwq

以前写过的题.........

$$O(n^2\log(u))$$

本题需要的知识
欧几里得
百度百科
扩展欧几里得
http://blog.csdn.net/zhjchengfeng5/article/details/7786595
裴蜀定理
百度百科
还有你还需要个 chh
给你讲讲
谢 大哥