记录编号	158145	评测结果	AAAAAAAAAA
题目名称	[HAOI 2012]高速公路	最终得分	100
用户昵称	Chenyao2333	是否通过	通过
代码语言	C++	运行时间	6.003 s
提交时间	2015-04-12 21:49:58	内存使用	9.08 MiB

#include<cstdio>
#include<algorithm>
#include<set>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const int L_N=1e5+10;
struct node{
    int ls,rs,fa;
    int sz;
    bool rev;
    LL lza,val;
    LL l,r,a,la,ra,lr,lra;
    node(){}
    node(LL ia){
        ls=rs=fa=rev=lza=0;
        sz=l=r=1, val=a=ia;
        la=l*a, ra=r*a, lr=l*r, lra=lr*a;
    }
}t[L_N];
void node_add(int x,LL a){
    if(!x) return;
    node & tt=t[x];
    tt.lza+=a;
    tt.val+=a;
    tt.a+=tt.sz*a;
    tt.la+=tt.l*a;
    tt.ra+=tt.r*a;
    tt.lra+=tt.lr*a;
}
void node_rev(int x){
    t[x].rev^=1;
    swap(t[x].l,t[x].r);
    swap(t[x].la,t[x].ra);
    swap(t[x].ls,t[x].rs);
}
void push_up(int x){
    if(!x) return;
    node & tt=t[x];
    node & ls=t[tt.ls];
    node & rs=t[tt.rs];
    tt.sz=ls.sz+rs.sz+1;
     
    LL lr=(ls.sz+1ll)*(rs.sz+1ll);
    LL add_r=(rs.sz+1ll);
    LL add_l=(ls.sz+1ll);
     
    tt.a=ls.a+rs.a+tt.val;
 
    tt.l=ls.l+(rs.l+rs.sz*add_l)+ls.sz+1;
    tt.r=rs.r+(ls.r+ls.sz*add_r)+rs.sz+1;
     
    tt.la=ls.la + (rs.la+rs.a*add_l) + (ls.sz+1)*tt.val;
    tt.ra=rs.ra + (ls.ra+ls.a*add_r) + (rs.sz+1)*tt.val;
 
    tt.lr=(ls.lr+ls.l*add_r) + (rs.lr+rs.r*add_l) + lr;
 
    tt.lra=(ls.lra+ls.la*add_r) + (rs.lra+rs.ra*add_l) + lr*tt.val;
}
void push_down(int x){
    if(!x) return;
    if(t[x].lza){
        node_add(t[x].ls,t[x].lza);
        node_add(t[x].rs,t[x].lza);
        t[x].lza=0;
    }
    if(t[x].rev){
        node_rev(t[x].ls);
        node_rev(t[x].rs);
        t[x].rev^=1;
    }
}
 
void zig(int x){
    if(!x) return;
    int y=t[x].fa, z=t[y].fa;
    if(t[z].ls==y) t[z].ls=x;
    if(t[z].rs==y) t[z].rs=x;
    t[x].fa=z;
    t[y].ls=t[x].rs, t[t[x].rs].fa=y;
    t[x].rs=y, t[y].fa=x;
    push_up(y), push_up(x);
}
 
void zag(int x){
    if(!x) return;
    int y=t[x].fa, z=t[y].fa;
    if(t[z].ls==y) t[z].ls=x;
    if(t[z].rs==y) t[z].rs=x;
    t[x].fa=z;
    t[y].rs=t[x].ls, t[t[x].ls].fa=y;
    t[x].ls=y, t[y].fa=x;
    push_up(y), push_up(x);
}
 
bool is_root(int x){
    return t[t[x].fa].ls!=x && t[t[x].fa].rs!=x;
}
void splay(int x){
    if(!x) return;
    push_down(x);
    while(!is_root(x)){
        int y=t[x].fa, z=t[y].fa;
        push_down(z), push_down(y), push_down(x); 
        if(is_root(y)){
            if(t[y].ls==x) zig(x);
            else zag(x);
            break;
        }else if(t[z].ls==y){
            if(t[y].ls==x) zig(y), zig(x);
            else zag(x), zig(x);
        }else if(t[z].rs==y){
            if(t[y].rs==x) zag(y), zag(x);
            else zig(x), zag(x);
        }
    }
}
 
void access(int x){
    if(!x) return;
    splay(x);
    for(int lst=0;x;lst=x, x=t[x].fa){
        splay(x);
        push_down(x);
        t[x].rs=lst;
        if(lst) t[lst].fa=x;
        push_up(x);
    }
}
 
void make_root(int x){
    if(!x) return;
    access(x), splay(x);
    node_rev(x), push_down(x);
}
 
int get_fa(int x){
    while(t[x].fa) x=t[x].fa;
    return x;
}
 
set<PII> es;
void cut(int u,int v){
    if(u>v) swap(u,v); if(u==v) return;
    if(!es.count(PII(u,v))) return;
    es.erase(PII(u,v));
    make_root(u), access(v), splay(u);
    t[v].fa=0,t[u].rs=0;
    push_up(u);
}
void link(int u,int v){
    if(u>v) swap(u,v); if(u==v) return;
    es.insert(PII(u,v));
    make_root(v), splay(v);
    t[v].fa=u;
}
 
 
int N,M;
LL gcd(LL a,LL b){
    if(!b) return a;
    return gcd(b,a%b);
}
int main(){
    freopen("roadxw.in","r",stdin);
    freopen("roadxw.out","w",stdout);
    //freopen("1.out","w",stdout);
    scanf("%d %d",&N,&M);
    for(int i=1;i<=N;i++){
        t[i]=node(0);
        if(i>1)link(i,i-1);
    }
     
    for(int i=1;i<=M;i++){
    	char op[2]; scanf("%s",&op);
        int u,v,d; scanf("%d %d",&u,&v); v--;
        switch(op[0]){
            case 'C':{
                scanf("%d",&d);
                int uf=get_fa(u), vf=get_fa(v);
                if(uf!=vf) continue;
                make_root(u), access(v), splay(v);
                node_add(v,d), push_down(v);
                break;
            }case 'Q':{
                int uf=get_fa(u), vf=get_fa(v);
                if(uf!=vf){
                    printf("-1\n");
                    break;
                }
 
                make_root(u), access(v), splay(v);
                LL val=t[v].lra, n=t[v].sz;
                n=n*(n+1)/2;
                LL d=gcd(val,n);
                if(d<0){
                    printf("QAQ\n");
                }
                printf("%lld/%lld\n",val/d,n/d);
                break;
            }
        }
    }
    return 0;
}