@ivorysi 2018-01-02T08:34:00.000000Z 字数 32445 阅读 770

数据结构(1)学习笔记

笔记

线段树

POJ 2828 Buy Tickets

Description

Railway tickets were difficult to buy around the Lunar New Year in China, so we must get up early and join a long queue…
The Lunar New Year was approaching, but unluckily the Little Cat still had schedules going here and there. Now, he had to travel by train to Mianyang, Sichuan Province for the winter camp selection of the national team of Olympiad in Informatics.
It was one o’clock a.m. and dark outside. Chill wind from the northwest did not scare off the people in the queue. The cold night gave the Little Cat a shiver. Why not find a problem to think about? That was none the less better than freezing to death!
People kept jumping the queue. Since it was too dark around, such moves would not be discovered even by the people adjacent to the queue-jumpers. “If every person in the queue is assigned an integral value and all the information about those who have jumped the queue and where they stand after queue-jumping is given, can I find out the final order of people in the queue?” Thought the Little Cat.

Input

There will be several test cases in the input. Each test case consists of N + 1 lines where N (1 ≤ N ≤ 200,000) is given in the first line of the test case. The next N lines contain the pairs of values Posi and Vali in the increasing order of i (1 ≤ i ≤ N). For each i, the ranges and meanings of Posi and Vali are as follows:
Posi ∈ [0, i − 1] — The i-th person came to the queue and stood right behind the Posi-th person in the queue. The booking office was considered the 0th person and the person at the front of the queue was considered the first person in the queue.
Vali ∈ [0, 32767] — The i-th person was assigned the value Vali.
There no blank lines between test cases. Proceed to the end of input.

Output

For each test cases, output a single line of space-separated integers which are the values of people in the order they stand in the queue.

Sample Input

4
0 77
1 51
1 33
2 69
4
0 20523
1 19243
1 3890
0 31492

Sample Output

77 33 69 51
31492 20523 3890 19243

Hint

The figure below shows how the Little Cat found out the final order of people in the queue described in the first test case of the sample input.

题解

这道题很秒啊！
可以考虑离线处理
最后一次插入的位置一定是准确的
从后往前处理，每次找到对应的位置即可

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <cmath>
#define siji(i,x,y) for(int i=(x);i<=(y);++i)
#define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
#define MOD 974711
#define MAXN 2000005
//#define ivorysi
using namespace std;
typedef long long ll;
struct node {
    int l,r;
    int sum;
}tr[MAXN*2];
void build (int u,int l,int r) {
    tr[u].l=l;
    tr[u].r=r;
    if(l==r) {
    tr[u].sum=1;
    return;
    }
    int mid=(l+r)>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
    tr[u].sum=r-l+1;
}
int findpos(int u,int x) {
    if(tr[u].l==tr[u].r) {
    tr[u].sum=0;
    return tr[u].l;
    }
    tr[u].sum--;
    if(tr[u<<1].sum>=x) {
    return findpos(u<<1,x);
    }
    else {
    return findpos(u<<1|1,x-tr[u<<1].sum);
    }
}
int n;
int pos[MAXN],val[MAXN];
int ans[MAXN];
void solve() {
    build(1,1,n);
    siji(i,1,n) {
    scanf("%d%d",&pos[i],&val[i]);
    }
    gongzi(i,n,1) {
    int x=findpos(1,pos[i]+1);
    ans[x]=val[i];
    }
    siji(i,1,n) {
    printf("%d%c",ans[i]," \n"[i==n]);
    }
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    while(scanf("%d",&n)!=EOF) {
    solve();
    }
    return 0;
}

codeforce 717 F. Heroes of Making Magic III

I’m strolling on sunshine, yeah-ah! And doesn’t it feel good! Well, it certainly feels good for our Heroes of Making Magic, who are casually walking on a one-directional road, fighting imps. Imps are weak and feeble creatures and they are not good at much. However, Heroes enjoy fighting them. For fun, if nothing else.
Our Hero, Ignatius, simply adores imps. He is observing a line of imps, represented as a zero-indexed array of integers a of length n, where ai denotes the number of imps at the i-th position. Sometimes, imps can appear out of nowhere. When heroes fight imps, they select a segment of the line, start at one end of the segment, and finish on the other end, without ever exiting the segment. They can move exactly one cell left or right from their current position and when they do so, they defeat one imp on the cell that they moved to, so, the number of imps on that cell decreases by one. This also applies when heroes appear at one end of the segment, at the beginning of their walk.
Their goal is to defeat all imps on the segment, without ever moving to an empty cell in it (without imps), since they would get bored. Since Ignatius loves imps, he doesn’t really want to fight them, so no imps are harmed during the events of this task. However, he would like you to tell him whether it would be possible for him to clear a certain segment of imps in the above mentioned way if he wanted to.
You are given q queries, which have two types:
1 a b k — denotes that k imps appear at each cell from the interval [a, b]
2 a b - asks whether Ignatius could defeat all imps on the interval [a, b] in the way described above

Input

The first line contains a single integer n (1 ≤ n ≤ 200 000), the length of the array a. The following line contains n integers a1, a2, ..., an (0 ≤ ai ≤ 5 000), the initial number of imps in each cell. The third line contains a single integer q (1 ≤ q ≤ 300 000), the number of queries. The remaining q lines contain one query each. Each query is provided by integers a, b and, possibly, k (0 ≤ a ≤ b < n, 0 ≤ k ≤ 5 000).

Output

For each second type of query output 1 if it is possible to clear the segment, and 0 if it is not.

Example

Input

3
2 2 2
3
2 0 2
1 1 1 1
2 0 2

Output

0
1

Note

For the first query, one can easily check that it is indeed impossible to get from the first to the last cell while clearing everything. After we add 1 to the second position, we can clear the segment, for example by moving in the following way:

题解

这算是比较难的线段树了
看完题发现根本不会

我们假定英雄都是从左边开始走，从右开始走可以作为从左走反过来

$a_{l}>=1$
$a_{l+1}-a_{l}>=0$
$a_{l+2}-(a_{l+1}-a_{l}+1)>=0$ 得到 $a_{l+2}-a_{l+1}+a_{l}>=1$
然后我们发现奇数个数我们要判断这个东西是否大于1
偶数个数判断这个东西是否大于0
我们设d[i]=a[i]-a[i-1]+a[i-2]-a[i-3]+a[i-4]...到a[1]
要判断一个区间 $[l,r]$ 是否合法
如果r-l+1是偶数
那么 $[l,r]$ 的d值是d[r]+d[l-1]
这个d值需要>=0
如果r-l+1是奇数
那么 $[l,r]$ 的d值是d[r]-d[l-1]
这个d值需要>=1
我们可以用分成奇偶位置来维护线段树
还要维护最小值来判断中间有没有不合法的情况出现

区间加的时候对于区间内的数，如果和l奇偶性相同就+k
去过区间长度是偶数，那么这个区间后面的数都可以不考虑，如果区间长度是奇数，和l奇偶性相同的就+k和
l奇偶性不同的就-k

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <cmath>
#define siji(i,x,y) for(int i=(x);i<=(y);++i)
#define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
#define MOD 974711
#define MAXN 200005
//#define ivorysi
using namespace std;
typedef long long ll;
struct node {
    int l,r;
    ll d,lazy,minq;
}tr[2][MAXN*10];
int n,q;
ll a[MAXN];
typedef int (*pf) (int);
void build(int now,int u,int l,int r,pf cur) {
    tr[now][u].l=l;
    tr[now][u].r=r;
    if(l==r) {
    tr[now][u].d=a[cur(l)];
    tr[now][u].minq=a[cur(l)];
    return;
    }
    int mid=(l+r)>>1;
    build(now,u<<1,l,mid,cur);
    build(now,u<<1|1,mid+1,r,cur);
    tr[now][u].minq=min(tr[now][u<<1].minq,tr[now][u<<1|1].minq);
}
int op1(int k) {
    return k*2;
}
int op2(int k) {
    return k*2-1;
}
void pushnode(int now,int u) {
    if(tr[now][u].lazy!=0) {
    tr[now][u<<1].d+=tr[now][u].lazy;
    tr[now][u<<1|1].d+=tr[now][u].lazy;
    tr[now][u<<1].minq+=tr[now][u].lazy;
    tr[now][u<<1|1].minq+=tr[now][u].lazy;
    tr[now][u<<1].lazy+=tr[now][u].lazy;
    tr[now][u<<1|1].lazy+=tr[now][u].lazy;
    tr[now][u].lazy=0;
    }
}
ll findval(int now,int u,int x,pf cur) {
    if(tr[now][u].l==tr[now][u].r) {
    return tr[now][u].d;
    }
    pushnode(now,u);
    int mid=(tr[now][u].l+tr[now][u].r)>>1;
    if(cur(mid)>=x) {
    return findval(now,u<<1,x,cur);
    }
    else {
    return findval(now,u<<1|1,x,cur);
    }
}
ll qmin(int now,int u,int l,int r) {
    if(tr[now][u].l==l && tr[now][u].r==r) {
    return tr[now][u].minq;
    }
    pushnode(now,u);
    int mid=(tr[now][u].l+tr[now][u].r)>>1;
    if(mid>=r) {
    return qmin(now,u<<1,l,r);
    }
    else if(mid<l) {
    return qmin(now,u<<1|1,l,r);
    }
    else {
    return min(qmin(now,u<<1,l,mid),qmin(now,u<<1|1,mid+1,r));
    }
}
ll getnode(int x) {
    if(x==0) return 0;
    if(x%2==0) {
    return findval(0,1,x,op1);
    }
    else {
    return findval(1,1,x,op2);
    }
}
void change(int now,int u,int l,int r,ll k) {
    if(tr[now][u].l==l && tr[now][u].r==r) {
    tr[now][u].lazy+=k;
    tr[now][u].minq+=k;
    tr[now][u].d+=k;
    return;
    }
    pushnode(now,u);
    int mid=(tr[now][u].l+tr[now][u].r)>>1;
    if(mid>=r) {
    change(now,u<<1,l,r,k);
    }
    else if(mid<l) {
    change(now,u<<1|1,l,r,k);
    }
    else {
    change(now,u<<1,l,mid,k);
    change(now,u<<1|1,mid+1,r,k);
    }
    tr[now][u].minq=min(tr[now][u<<1].minq,tr[now][u<<1|1].minq);
}
int leftpos_odd(int l) {//这道题直接算点是做不到的……
    if(l%2==0) ++l;
    return (l+1)/2;
}
int rightpos_odd(int r) {
    if(r%2==0) --r;
    return (r+1)/2;
}
int leftpos_even(int l) {
    if(l%2) ++l;
    return l/2;       
}
int rightpos_even(int r) {
    if(r%2) --r;
    return r/2;
}
void solve() {
    scanf("%d",&n);
    siji(i,1,n) {
    scanf("%lld",&a[i]);
    }
    siji(i,2,n) {
    a[i]=a[i]-a[i-1];
    }
    build(0,1,leftpos_even(1),rightpos_even(n),op1);
    build(1,1,leftpos_odd(1),rightpos_odd(n),op2);
    scanf("%d",&q);
    int op,a,b;
    ll k;
    siji(i,1,q) {
    if(scanf("%d%d%d",&op,&a,&b)==EOF) break;
    ++a,++b;
    if(op==1) {
        scanf("%lld",&k);
        int now=a%2;
        if(now==1) {
        change(now,1,leftpos_odd(a),rightpos_odd(b),k);
        }
        else {
        change(now,1,leftpos_even(a),rightpos_even(b),k);
        }
        if((b-a+1)%2) {
        ++b;
        if(b>n) continue;
        if(a%2==0) {
            if(rightpos_even(n)>=leftpos_even(b)) {
            change(0,1,leftpos_even(b),rightpos_even(n),k);
            }
            if(rightpos_odd(n)>=leftpos_odd(b)) {
            change(1,1,leftpos_odd(b),rightpos_odd(n),-k);
            }
        }
        else {
            if(rightpos_even(n)>=leftpos_even(b)) {
            change(0,1,leftpos_even(b),rightpos_even(n),-k);
            }
            if(rightpos_odd(n)>=leftpos_odd(b)) {
            change(1,1,leftpos_odd(b),rightpos_odd(n),k);
            }
        }
        }
    }
    else {
        ll d1=getnode(b),d2=getnode(a-1);
        if(a==b) {
        d1+=d2;
        if(d1!=1) puts("0");
        else puts("1");
        continue;
        }
        ll t1,t2;
        if(rightpos_even(b)>=leftpos_even(a)) {
        t1=qmin(0,1,leftpos_even(a),rightpos_even(b));
        if((a-1)%2==0 && t1-d2<0) {puts("0");continue;}
        if((a-1)%2==1 && t1+d2<1) {puts("0");continue;}
        }
        if(rightpos_odd(b)>=leftpos_odd(a)) {
        t2=qmin(1,1,leftpos_odd(a),rightpos_odd(b));
        if((a-1)%2==1 && t2-d2<0) {puts("0");continue;}
        if((a-1)%2==0 && t2+d2<1) {puts("0");continue;}
        }
        int len=b-a+1;
        if(len%2==0) {
        d1-=d2;
        }
        else {
        d1+=d2;
        }
        if(d1==(len%2)) puts("1");
        else puts("0");
    }
    }
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    solve();
    return 0;
}

codeforce 498 D. Traffic Jams in the Land

Some country consists of (n + 1) cities, located along a straight highway. Let's number the cities with consecutive integers from 1 to n + 1 in the order they occur along the highway. Thus, the cities are connected by n segments of the highway, the i-th segment connects cities number i and i + 1. Every segment of the highway is associated with a positive integer ai > 1 — the period of traffic jams appearance on it.
In order to get from city x to city y (x < y), some drivers use the following tactics.
Initially the driver is in city x and the current time t equals zero. Until the driver arrives in city y, he perfors the following actions:
if the current time t is a multiple of ax, then the segment of the highway number x is now having traffic problems and the driver stays in the current city for one unit of time (formally speaking, we assign t = t + 1);
if the current time t is not a multiple of ax, then the segment of the highway number x is now clear and that's why the driver uses one unit of time to move to city x + 1 (formally, we assign t = t + 1 and x = x + 1).
You are developing a new traffic control system. You want to consecutively process q queries of two types:
determine the final value of time t after the ride from city x to city y (x < y) assuming that we apply the tactics that is described above. Note that for each query t is being reset to 0.
replace the period of traffic jams appearing on the segment number x by value y (formally, assign ax = y).
Write a code that will effectively process the queries given above.

Input

The first line contains a single integer n (1 ≤ n ≤ 105) — the number of highway segments that connect the n + 1 cities.
The second line contains n integers a1, a2, ..., an (2 ≤ ai ≤ 6) — the periods of traffic jams appearance on segments of the highway.
The next line contains a single integer q (1 ≤ q ≤ 105) — the number of queries to process.
The next q lines contain the descriptions of the queries in the format c, x, y (c — the query type).
If c is character 'A', then your task is to process a query of the first type. In this case the following constraints are satisfied: 1 ≤ x < y ≤ n + 1.
If c is character 'C', then you need to process a query of the second type. In such case, the following constraints are satisfied: 1 ≤ x ≤ n, 2 ≤ y ≤ 6.

Output

For each query of the first type output a single integer — the final value of time t after driving from city x to city y. Process the queries in the order in which they are given in the input.

题解

这道题建60棵线段树，因为2 3 4 5 6的最大公倍数是60
[l,r]区间表示从l开始值%60开始所要花的最大时间
每次更新区间更新60次
然后用左区间用的时间+当前时间赋给右区间去累加

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <cmath>
#define siji(i,x,y) for(int i=(x);i<=(y);++i)
#define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
#define MOD 974711
#define MAXN 100005
//#define ivorysi
using namespace std;
typedef long long ll;
struct node {
    int l,r;
    int val[60];
}tr[MAXN*4];
int n,q;
int a[MAXN],x,y;
char str[5];
void build(int u,int l,int r) {
    tr[u].l=l;tr[u].r=r;
    if(l==r) {
    siji(i,0,59) {
        tr[u].val[i]=1+(i%a[l]==0);
    }
    return;
    }
    int mid=(l+r)>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
    siji(i,0,59) {
    int lsum=tr[u<<1].val[i];
    int rsum=tr[u<<1|1].val[(i+lsum)%60];
    tr[u].val[i]=lsum+rsum;
    }
    return;
}
void changepos(int u,int x) {
    if(tr[u].l==tr[u].r) {
    siji(i,0,59) {
        tr[u].val[i]=1+(i%a[x]==0);
    }
    return;
    }
    int mid=(tr[u].l+tr[u].r)>>1;
    if(x<=mid) {
    changepos(u<<1,x);
    }
    else {
    changepos(u<<1|1,x);
    }
    siji(i,0,59) {
    int lsum=tr[u<<1].val[i];
    int rsum=tr[u<<1|1].val[(i+lsum)%60];
    tr[u].val[i]=lsum+rsum;
    }
}
int query(int u,int l,int r,int s) {
    if(tr[u].l==l && tr[u].r==r) {
    return tr[u].val[s];
    }
    int mid=(tr[u].l+tr[u].r)>>1;
    if(r<=mid) {
    return query(u<<1,l,r,s);
    }
    else if(l>mid) {
    return query(u<<1|1,l,r,s);
    }
    else {
    int lsum=query(u<<1,l,mid,s);
    int rsum=query(u<<1|1,mid+1,r,(s+lsum)%60);
    return lsum+rsum;
    }
}
void solve() {
    scanf("%d",&n);
    siji(i,1,n) {
    scanf("%d",&a[i]);
    }
    build(1,1,n);
    scanf("%d",&q);
    siji(i,1,q) {
    scanf("%s",str+1);
    scanf("%d%d",&x,&y);
    if(str[1]=='A') {
        --y;
        printf("%d\n",query(1,x,y,0));
    }
    else {
        a[x]=y;
        changepos(1,x);
    }
    }
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    solve();
    return 0;
}

树状数组

POJ 1990 MooFest

Description

Every year, Farmer John's N (1 <= N <= 20,000) cows attend "MooFest",a social gathering of cows from around the world. MooFest involves a variety of events including haybale stacking, fence jumping, pin the tail on the farmer, and of course, mooing. When the cows all stand in line for a particular event, they moo so loudly that the roar is practically deafening. After participating in this event year after year, some of the cows have in fact lost a bit of their hearing.
Each cow i has an associated "hearing" threshold v(i) (in the range 1..20,000). If a cow moos to cow i, she must use a volume of at least v(i) times the distance between the two cows in order to be heard by cow i. If two cows i and j wish to converse, they must speak at a volume level equal to the distance between them times max(v(i),v(j)).
Suppose each of the N cows is standing in a straight line (each cow at some unique x coordinate in the range 1..20,000), and every pair of cows is carrying on a conversation using the smallest possible volume.
Compute the sum of all the volumes produced by all N(N-1)/2 pairs of mooing cows.

Input

Line 1: A single integer, N

Lines 2..N+1: Two integers: the volume threshold and x coordinate for a cow. Line 2 represents the first cow; line 3 represents the second cow; and so on. No two cows will stand at the same location.

Output

Line 1: A single line with a single integer that is the sum of all the volumes of the conversing cows.

Sample Input

4
3 1
2 5
2 6
4 3

Sample Output

57

题解

这道题把v从小到大排序
然后求去在它前面的点到它的距离总和，在它后面的点到它的距离总和
两个树状数组即可

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <cmath>
#define siji(i,x,y) for(int i=(x);i<=(y);++i)
#define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
#define MOD 974711
#define MAXN 20005
//#define ivorysi
using namespace std;
typedef long long ll;
struct node {
    int v,x;
    bool operator < (const node &rhs) const{
    return v<rhs.v;
    }
}cow[MAXN];
ll tr1[MAXN],tr2[MAXN],ans;
int n;
int lowbit(int x) {return x&(-x);}
void change(ll *cur,int pos,ll x) {
    while(pos<=20000) {
    cur[pos]+=x;
    pos+=lowbit(pos);
    }
}
ll getval(ll *cur,int pos){
    ll res=0;
    while(pos) {
    res+=cur[pos];
    pos-=lowbit(pos);
    }
    return res;
}
ll query(ll *cur,int l,int r) {
    return getval(cur,r)-getval(cur,l-1);
}
void solve() {
    scanf("%d",&n);
    siji(i,1,n) {
    scanf("%d%d",&cow[i].v,&cow[i].x);
    }
    sort(cow+1,cow+n+1);
    siji(i,1,n) {
    ll len=(query(tr1,1,cow[i].x-1)*cow[i].x-query(tr2,1,cow[i].x-1))+
        (query(tr2,cow[i].x+1,20000)-query(tr1,cow[i].x+1,20000)*cow[i].x);
    len=len*cow[i].v;
    ans+=len;
    change(tr1,cow[i].x,1);
    change(tr2,cow[i].x,cow[i].x);
    }
    printf("%lld\n",ans);
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    solve();
    return 0;
}

ST表

codeforce 359 D. Pair of Numbers

Simon has an array a1, a2, ..., an, consisting of n positive integers. Today Simon asked you to find a pair of integers l, r (1 ≤ l ≤ r ≤ n), such that the following conditions hold:

there is integer j (l ≤ j ≤ r), such that all integers al, al + 1, ..., ar are divisible by aj;
value r - l takes the maximum value among all pairs for which condition 1 is true;

Help Simon, find the required pair of numbers (l, r). If there are multiple required pairs find all of them.

Input

The first line contains integer n (1 ≤ n ≤ 3·105).
The second line contains n space-separated integers a1, a2, ..., an (1 ≤ ai ≤ 106).

Output

Print two integers in the first line — the number of required pairs and the maximum value of r - l. On the following line print all l values from optimal pairs in increasing order.
Examples

Input

5
4 6 9 3 6

Output

1 3
2

Input

5
1 3 5 7 9

Output

1 4
1

Input

5
2 3 5 7 11

Output

5 0
1 2 3 4 5

Note

In the first sample the pair of numbers is right, as numbers 6, 9, 3 are divisible by 3.
In the second sample all numbers are divisible by number 1.
In the third sample all numbers are prime, so conditions 1 and 2 are true only for pairs of numbers (1, 1), (2, 2), (3, 3), (4, 4), (5, 5).

题解

这个区间所有的数的gcd和最小值是一个的话那么这个区间就是合法的
用st表维护就行，二分答案

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#define siji(i,x,y) for(int i=(x);i<=(y);++i)
#define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
#define MOD 974711
#define MAXN 300005
//#define ivorysi
using namespace std;
typedef long long ll;
int n;
int a[MAXN];
int st1[MAXN][25],st2[MAXN][25];
int log2[MAXN];
vector<int> v;
int gcd(int a,int b) {
    return b==0 ? a:gcd(b,a%b);
}
int query1(int a,int b) {
    int l=log2[b-a+1];
    return gcd(st1[a][l],st1[b-(1<<l)+1][l]);
}
int query2(int a,int b) {
    int l=log2[b-a+1];
    return min(st2[a][l],st2[b-(1<<l)+1][l]);
}
bool check(int x) {
    siji(i,1,n) {
    if(i+x>n) return false;
    if(query1(i,i+x)==query2(i,i+x)) {
        return true;
    }
    }
    return false;
}
void solve() {
    scanf("%d",&n);
    siji(i,1,n) {
    scanf("%d",&a[i]);
    }
    siji(i,2,n) {
    int t=i;
    int l=0;
    while(t) {++l;t>>=1;}
    --l;
    log2[i]=l;
    }
    siji(i,1,n) {
    st1[i][0]=a[i];
    st2[i][0]=a[i];
    }
    siji(j,1,20) {
    siji(i,1,n) {
        if(i+(1<<j)-1 > n) break;
        st1[i][j]=gcd(st1[i][j-1],st1[i+(1<<(j-1))][j-1]);
        st2[i][j]=min(st2[i][j-1],st2[i+(1<<(j-1))][j-1]);
    }
    }
    int l=0,r=n-1;
    while(l<r) {
    int mid=(l+r+1)>>1;
    if(check(mid)) l=mid;
    else r=mid-1;
    }
    siji(i,1,n) {
    if(i+l>n) break;
    if(query1(i,i+l)==query2(i,i+l)) {
        v.push_back(i);
    }
    }
    int s=v.size();
    printf("%d %d\n",s,l);
    xiaosiji(i,0,s) {
    printf("%d%c",v[i]," \n"[i==s-1]);
    }
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    solve();
    return 0;
}

左偏树

如何愉快的书写这个比堆还好写的可并堆呢
两个堆合并的话（假设小根堆）
如果A或B一个堆为空，返回另一个
我们将A的右儿子和B合并（如果A的根权值比B大就交换AB）
然后比较A左右子树的距离，如果右子树的距离比较大，把左右子树交换
更新A的距离
返回A

删除根节点只需要合并两个子树就好了

BZOJ 2809: [Apio2012]dispatching

Description

在一个忍者的帮派里，一些忍者们被选中派遣给顾客，然后依据自己的工作获取报偿。在这个帮派里，有一名忍者被称之为 Master。除了 Master以外，每名忍者都有且仅有一个上级。为保密，同时增强忍者们的领导力，所有与他们工作相关的指令总是由上级发送给他的直接下属，而不允许通过其他的方式发送。现在你要招募一批忍者，并把它们派遣给顾客。你需要为每个被派遣的忍者支付一定的薪水，同时使得支付的薪水总额不超过你的预算。另外，为了发送指令，你需要选择一名忍者作为管理者，要求这个管理者可以向所有被派遣的忍者发送指令，在发送指令时，任何忍者（不管是否被派遣）都可以作为消息的传递人。管理者自己可以被派遣，也可以不被派遣。当然，如果管理者没有被排遣，就不需要支付管理者的薪水。你的目标是在预算内使顾客的满意度最大。这里定义顾客的满意度为派遣的忍者总数乘以管理者的领导力水平，其中每个忍者的领导力水平也是一定的。写一个程序，给定每一个忍者 i的上级 Bi，薪水Ci，领导力L i，以及支付给忍者们的薪水总预算 M，输出在预算内满足上述要求时顾客满意度的最大值。
1 ≤N ≤ 100,000 忍者的个数；
1 ≤M ≤ 1,000,000,000 薪水总预算；
0 ≤Bi < i 忍者的上级的编号；
1 ≤Ci ≤ M 忍者的薪水；
1 ≤Li ≤ 1,000,000,000 忍者的领导力水平。

Input

从标准输入读入数据。
第一行包含两个整数 N和 M，其中 N表示忍者的个数，M表示薪水的总预算。
接下来 N行描述忍者们的上级、薪水以及领导力。其中的第 i 行包含三个整 Bi , C i , L i分别表示第i个忍者的上级，薪水以及领导力。Master满足B i = 0，并且每一个忍者的老板的编号一定小于自己的编号 Bi < i。

Output

输出一个数，表示在预算内顾客的满意度的最大值。

Sample Input

5 4
0 3 3
1 3 5
2 2 2
1 2 4
2 3 1

Sample Output

6

题解

选择一个树上的点，然后选择这个树的一些子节点，这些子节点的和不超过m
然后我们可以对每个子树建一个左偏树，如果左偏树的总和大于m，就不断删除最大值直到总和小于m
然后更新ans就可以了

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#define siji(i,x,y) for(int i=(x);i<=(y);++i)
#define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
#define MOD 974711
#define MAXN 100005
//#define ivorysi
using namespace std;
typedef long long ll;
struct node {
    node *lc,*rc;
    int dist,size,val;
    long long sum;
    node() {}
    node(const int &c) {
    lc=NULL,rc=NULL,dist=0,size=1,val=c,sum=c;
    }
    inline void update() {
    sum=val,size=1;
    if(lc!=NULL)sum+=lc->sum,size+=lc->size;
    if(rc!=NULL)sum+=rc->sum,size+=rc->size;
    }
}*tr[MAXN];
struct data {
    int to,next;
}edge[MAXN+5];
int head[MAXN],sumedge;
void add(int u,int v) {
    edge[++sumedge].to=v;
    edge[sumedge].next=head[u];
    head[u]=sumedge;
}
int n;
int lead[MAXN],fa[MAXN],calc[MAXN],rt,que[MAXN],ql;
ll budget,ans;
int getdist(node *z){
    if(z==NULL) return -1;
    else return z->dist;
}
node* merge(node* A,node* B) {
    if(A==NULL) return B;
    if(B==NULL) return A;
    if(A->val < B->val) swap(A,B);
    A->rc=merge(A->rc,B);
    if(getdist(A->rc) > getdist(A->lc)) {
    swap(A->rc,A->lc);
    }
    A->dist=getdist(A->rc)+1;
    A->update();
    return A;
}
void balance(node *&x) {
    while(x->sum > budget) {
    x=merge(x->lc,x->rc);
    }
}
void solve() {
    scanf("%d%lld",&n,&budget);
    siji(i,1,n) {
    scanf("%d%d%d",&fa[i],&calc[i],&lead[i]);
    if(fa[i]==0) rt=i;
    else add(fa[i],i);
    tr[i]=new node(calc[i]);
    }
    que[++ql]=rt;
    siji(u,1,ql) {
    for(int i=head[u];i;i=edge[i].next) {
        que[++ql]=edge[i].to;
    }
    }
    gongzi(i,ql,2) {
    int now=que[i],y=fa[now];
    ans=max(ans,(ll)tr[now]->size*lead[now]);
    tr[y]=merge(tr[now],tr[y]);
    balance(tr[y]);
    }
    ans=max(ans,(ll)tr[rt]->size*lead[rt]);
    printf("%lld\n",ans);
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    solve();
    return 0;
}

POJ3666 Making the Grade

Description

A straight dirt road connects two fields on FJ's farm, but it changes elevation more than FJ would like. His cows do not mind climbing up or down a single slope, but they are not fond of an alternating succession of hills and valleys. FJ would like to add and remove dirt from the road so that it becomes one monotonic slope (either sloping up or down).
You are given N integers A1, ... , AN (1 ≤ N ≤ 2,000) describing the elevation (0 ≤ Ai ≤ 1,000,000,000) at each of N equally-spaced positions along the road, starting at the first field and ending at the other. FJ would like to adjust these elevations to a new sequence B1, . ... , BN that is either nonincreasing or nondecreasing. Since it costs the same amount of money to add or remove dirt at any position along the road, the total cost of modifying the road is
|A1 - B1| + |A2 - B2| + ... + |AN - BN |
Please compute the minimum cost of grading his road so it becomes a continuous slope. FJ happily informs you that signed 32-bit integers can certainly be used to compute the answer.

Input

Line 1: A single integer: N

Lines 2..N+1: Line i+1 contains a single integer elevation: Ai

Output

Line 1: A single integer that is the minimum cost for FJ to grade his dirt road so it becomes nonincreasing or nondecreasing in elevation.

Sample Input

7
1
3
2
4
5
3
9

Sample Output

3

题解

这道题我们要考虑两种情况
就按照如果我们要恢复的序列是非下降序列
如果a[1]<=a[2]<=a[3]<=a[4]...<=a[n]
那么我们这个序列显然不用动了
如果a[1]>a[2]>a[3]>a[4]...>a[n]
我们可以把这个区间全部改为这个区间的中位数
这样一定是最优的因为我们必须把区间修改成同一个数
然后我们的区间划分成为若干个下降序列（可以只有一个点）
如果这两个下降序列的中位数非下降，我们可以直接合并这两个区间
否则我们需要把这两个区间合并，找它们的中位数
为什么是对的呢，因为如果前面的区间的值如果大于后面的区间，后面的区间需要整体提升，然后提升到和前面的区间值一样为止
但是反正都是一样的值了，最优解就是他们的中位数
然后我们用一个队列维护一个区间，一个点建立一个区间
然后拿这个区间和队尾比较，如果这个点比前一个小，那么合并这个两个区间，直到这个队列里区间的中位数单调不下降
维护中位数用左偏树，如果左偏树里区间个数大于一半就删除

非上升序列也同理

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#define siji(i,x,y) for(int i=(x);i<=(y);++i)
#define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
#define MOD 974711
#define MAXN 100005
//#define ivorysi
using namespace std;
typedef long long ll;
struct node {
    node *lc,*rc;
    int dist,size,val;
    node() {};
    node(const int &v) {
    val=v;size=1;dist=0;lc=NULL;rc=NULL;
    }
    void update() {
    size=1;
    if(lc!=NULL) size+=lc->size;
    if(rc!=NULL) size+=rc->size;
    }
}*tr[MAXN];
int n;
int a[MAXN];
int getdist(node *z){
    if(z==NULL) return -1;
    else return z->dist;
}
node* merge(node* A,node* B) {
    if(A==NULL) return B;
    if(B==NULL) return A;
    if(A->val < B->val) swap(A,B);
    A->rc=merge(A->rc,B);
    if(getdist(A->rc) > getdist(A->lc)) {
    swap(A->rc,A->lc);
    }
    A->dist=getdist(A->rc)+1;
    A->update();
    return A;
}
void balance(node *&x,int len) {
    if(len%2) len=len/2+1;
    else len/=2;
    while(x->size>len) {
    x=merge(x->lc,x->rc);
    }
}
int b[MAXN];
int que[MAXN],ql;
ll ans;
void solve() {
    scanf("%d",&n);
    siji(i,1,n) {
    scanf("%d",&a[i]);
    }
    ql=0;
    siji(i,1,n) {
    b[i]=a[i];
    tr[i]=new node(a[i]);
    while(ql>0 && b[i]<b[que[ql]]) {
        tr[i]=merge(tr[i],tr[que[ql]]);
        --ql;
        balance(tr[i],i-que[ql]);
        b[i]=tr[i]->val;
    }
    que[++ql]=i;
    }
    int p=1,t=1;
    while(p<=n) {
    b[p]=b[que[t]];
    if(p==que[t]) ++t;
    ++p;
    }
    siji(i,1,n) {
    ans+=abs(a[i]-b[i]);
    }
    memset(tr,0,sizeof(tr));
    ql=0;
    siji(i,1,n) {
    b[i]=a[i];
    tr[i]=new node(a[i]);
    while(ql>0 && b[i]>b[que[ql]]) {
        tr[i]=merge(tr[i],tr[que[ql]]);
        --ql;
        balance(tr[i],i-que[ql]);
        b[i]=tr[i]->val;
    }
    que[++ql]=i;
    }
    p=1,t=1;
    while(p<=n) {
    b[p]=b[que[t]];
    if(p==que[t])++t;
    ++p;
    }
    ll tmp=0;
    siji(i,1,n) {
    tmp+=abs(a[i]-b[i]);
    }
    ans=min(ans,tmp);
    printf("%lld\n",ans);
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    solve();
    return 0;
}

树链剖分

一些要用的部分分别是
fa 每个点的父亲
size 每个点子树的大小（用来更新重儿子）
son 每个点的重儿子
dep 每个点的深度（用来爬树）
belong 每个点属于哪条链
top 这条链的顶端
lroot 这条链树根的编号

BZOJ 2243: [SDOI2011]染色

Description

给定一棵有n个节点的无根树和m个操作，操作有2类：
1、将节点a到节点b路径上所有点都染成颜色c；
2、询问节点a到节点b路径上的颜色段数量（连续相同颜色被认为是同一段），
如“112221”由3段组成：“11”、“222”和“1”。
请你写一个程序依次完成这m个操作。

Input

第一行包含2个整数n和m，分别表示节点数和操作数；
第二行包含n个正整数表示n个节点的初始颜色
下面行每行包含两个整数x和y，表示x和y之间有一条无向边。
下面行每行描述一个操作：
“C a b c”表示这是一个染色操作，把节点a到节点b路径上所有点（包括a和b）都染成颜色c；
“Q a b”表示这是一个询问操作，询问节点a到节点b（包括a和b）路径上的颜色段数量。

Output

对于每个询问操作，输出一行答案。

Sample Input

6 5
2 2 1 2 1 1
1 2
1 3
2 4
2 5
2 6
Q 3 5
C 2 1 1
Q 3 5
C 5 1 2
Q 3 5

Sample Output

3
1
2

HINT

数N<=10^5，操作数M<=10^5，所有的颜色C为整数且在[0, 10^9]之间。

题解

树链剖分又一道板子题级别的题
我们维护这个区间左右端点的颜色，如果左区间的右端点颜色和右区间的左端点颜色相同统计数就减一

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <cmath>
#define siji(i,x,y) for(int i=(x);i<=(y);++i)
#define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
#define MOD 974711
#define MAXN 100005
//#define ivorysi
using namespace std;
typedef long long ll;
struct treenode {
    int l,r,
        lson,
        rson,
        lcol,
        rcol,
        sum,
        setcol;
    bool lazy;
}tr[MAXN*10];
int treecnt;
void update(int u) {
    int ls=tr[u].lson,rs=tr[u].rson;
    tr[u].sum=tr[ls].sum+tr[rs].sum;
    if(tr[ls].rcol==tr[rs].lcol) --tr[u].sum;
    tr[u].lcol=tr[ls].lcol;
    tr[u].rcol=tr[rs].rcol; 
}
void pushnode(int u) {
    if(tr[u].lazy) {
        int ls=tr[u].lson,rs=tr[u].rson;
        tr[ls].sum=1;tr[ls].lcol=tr[ls].rcol=tr[u].setcol;
        tr[rs].sum=1;tr[rs].lcol=tr[rs].rcol=tr[u].setcol;
        tr[ls].lazy=tr[rs].lazy=1;
        tr[ls].setcol=tr[rs].setcol=tr[u].setcol;
        tr[u].setcol=0;tr[u].lazy=0;
    }
}
int dep[MAXN],
    fa[MAXN],
    size[MAXN],
    son[MAXN],
    rnk[MAXN],
    belong[MAXN],
    top[MAXN],
    linkcnt,
    lroot[MAXN];
int n,col[MAXN],m;
struct node {
    int to,next;
}edge[MAXN*2];
int head[MAXN],sumedge;
void add(int u,int v) {
    edge[++sumedge].to=v;
    edge[sumedge].next=head[u];
    head[u]=sumedge;
}
void addtwo(int u,int v) {
    add(u,v);
    add(v,u);
}
void dfs1(int u){
    size[u]=1;
    for(int i=head[u];i;i=edge[i].next) {
        int v=edge[i].to;
        if(v!=fa[u]) {
            fa[v]=u;
            dep[v]=dep[u]+1;
            dfs1(v);
            size[u]+=size[v];
            if(size[v]>size[son[u]]) son[u]=v;
        }
    }
}
void build(int u,int l,int r);
vector<int> line;
void dfs2(int u) {
    if(!belong[u]) {
        belong[u]=++linkcnt;
        top[belong[u]]=u;
        rnk[u]=1;
    }
    line.push_back(u);
    if(!son[u]) {
        lroot[belong[u]]=++treecnt;
        build(treecnt,1,rnk[u]);
        line.clear();
        return;
    }
    belong[son[u]]=belong[u];
    rnk[son[u]]=rnk[u]+1;
    dfs2(son[u]);
    for(int i=head[u];i;i=edge[i].next) {
        int v=edge[i].to;
        if(v!=son[u] && v!=fa[u]) {
            dfs2(v);
        }
    }
}
void build(int u,int l,int r) {
    tr[u].l=l;tr[u].r=r;
    if(l==r) {
        tr[u].sum=1;
        tr[u].lcol=col[line[l-1]];
        tr[u].rcol=col[line[l-1]];
        tr[u].lazy=0;
        return;
    }
    int mid=(l+r)>>1;
    tr[u].lson=++treecnt;tr[u].rson=++treecnt;
    build(tr[u].lson,l,mid);
    build(tr[u].rson,mid+1,r);
    update(u);
}
int query_tree(int u,int l,int r) {
    if(l==tr[u].l && r==tr[u].r) {
        return tr[u].sum;
    }
    int mid=(tr[u].l+tr[u].r)>>1;
    int ls=tr[u].lson,rs=tr[u].rson;
    pushnode(u);
    if(mid>=r) {
        return query_tree(ls,l,r);
    }
    else if(l>mid) {
        return query_tree(rs,l,r);
    }
    else {
        return query_tree(ls,l,mid)+query_tree(rs,mid+1,r)-(tr[ls].rcol==tr[rs].lcol);
    }
}
int ask_color(int u,int x) {
    if(tr[u].l==tr[u].r) {
        return tr[u].lcol;
    }
    pushnode(u);
    int mid=(tr[u].l+tr[u].r)>>1;
    if(x<=mid) {
        return ask_color(tr[u].lson,x);
    }
    else {
        return ask_color(tr[u].rson,x);
    }
}
void change_tree(int u,int l,int r,int c) {
    if(l==tr[u].l && r==tr[u].r) {
        tr[u].sum=1;
        tr[u].lazy=1;
        tr[u].setcol=c;
        tr[u].lcol=tr[u].rcol=c;
        return ;
    }
    pushnode(u);
    int mid=(tr[u].l+tr[u].r)>>1;
    int ls=tr[u].lson,rs=tr[u].rson;
    if(r<=mid) {
        change_tree(ls,l,r,c);
    }
    else if(l>mid) {
        change_tree(rs,l,r,c);
    }
    else {
        change_tree(ls,l,mid,c);
        change_tree(rs,mid+1,r,c);
    }
    update(u);
}
int query(int a,int b) {
    int res=0;
    while(belong[a]!=belong[b]) {
        if(dep[top[belong[a]]]<dep[top[belong[b]]]) swap(a,b);
        int l=fa[top[belong[a]]];
        int z=lroot[belong[a]];
        res+=query_tree(z,1,rnk[a]);
        if(tr[z].lcol==ask_color(lroot[belong[l]],rnk[l])) {
            --res;
        }
        a=l;
    }
    if(rnk[a]>rnk[b]) swap(a,b);
    res+=query_tree(lroot[belong[a]],rnk[a],rnk[b]);
    return res;
}
void change(int a,int b,int c) {
    while(belong[a]!=belong[b]) {
        if(dep[top[belong[a]]]<dep[top[belong[b]]]) swap(a,b);
        int z=lroot[belong[a]];
        int l=fa[top[belong[a]]];
        change_tree(z,1,rnk[a],c);
        a=l;
    }
    if(rnk[a]>rnk[b]) swap(a,b);
    change_tree(lroot[belong[a]],rnk[a],rnk[b],c);
}
void prepare() {
    scanf("%d%d",&n,&m);
    siji(i,1,n) {
        scanf("%d",&col[i]);
    }
    int u,v;
    xiaosiji(i,1,n) {
        scanf("%d%d",&u,&v);
        addtwo(u,v);
    }
    dep[1]=1;
    dfs1(1);dfs2(1);
}
void solve() {
    prepare();
    char s[5];
    int a,b,c;
    siji(i,1,m) {
        scanf("%s",s+1);
        if(s[1]=='Q') {
            scanf("%d%d",&a,&b);
            printf("%d\n",query(a,b));
        }
        else {
            scanf("%d%d%d",&a,&b,&c);
            change(a,b,c);
        }
    }
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    solve();
    return 0; 
}

CC DGCD

All submissions for this problem are available.
You're given a tree on N vertices. Each vertex has a positive integer written on it, number on the ith vertex being vi. Your program must process two types of queries :
1. Find query represented by F u v : Find out gcd of all numbers on the unique path between vertices u and v in the tree (both inclusive).
2. Change query represented by C u v d : Add d to the number written on all vertices along the unique path between vertices u and v in the tree (both inclusive).

Input

First line of input contains an integer N denoting the size of the vertex set of the tree. Then follow N - 1 lines, ith of which contains two integers ai and bi denoting an edge between vertices ai and bi in the tree. After this follow N space separated integers in a single line denoting initial values vi at each of these nodes. Then follows a single integer Q on a line by itself, denoting the number of queries to follow. Then follow Q queries, each one on a line by itself. Each query is either a find query or a change query with format as given in problem statement. Note that all vertices are 0-based.

Output

For every find query, print the answer to that query in one line by itself.

Input:

6
0 4
0 5
1 5
5 2
3 5
3 1 3 2 4 2
5
F 3 5
C 1 3 1
C 3 4 4
F 3 0
F 2 5

Output:

2
7
1

Constraints

1 <= N <= 50000
1 <= Q <= 50000
0 <= u, v <= N-1
1 <= vi <= 10^4
0 <= d <= 10^4

题解

这道题考虑这样一件事
$k|g$
$m|g$
$m-k|g$
进行累加后
$k+d|g$
$m+d|g$
$m-k|g$
很妙的是，m-k显然没有变啊
所以我们考虑差分，计算所有差分的gcd，然后用第一个数的原值和这个gcd计算gcd即可
这样线段树上的维护只需要单点修改
（如何把一道线段树的题变得非常恶心）
（你只需要一棵树就够了）

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <cmath>
#define siji(i,x,y) for(int i=(x);i<=(y);++i)
#define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
#define MOD 974711
#define MAXN 100005
//#define ivorysi
using namespace std;
typedef long long ll;
struct treenode {
    int l,r,
        lson,
        rson,
        val,
        sum;
    bool lazy;
}tr[MAXN*10];
int treecnt;
int gcd(int a,int b) {
    return b==0 ? a:gcd(b,a%b);
}
void update(int u) {
    int ls=tr[u].lson,rs=tr[u].rson;
    tr[u].val=gcd(abs(tr[ls].val),abs(tr[rs].val));
    tr[u].sum=tr[ls].sum+tr[rs].sum;
}
int dep[MAXN],
    fa[MAXN],
    size[MAXN],
    son[MAXN],
    rnk[MAXN],
    belong[MAXN],
    top[MAXN],
    linkcnt,
    lroot[MAXN];
int n,num[MAXN],m;
struct node {
    int to,next;
}edge[MAXN*2];
int head[MAXN],sumedge;
void add(int u,int v) {
    edge[++sumedge].to=v;
    edge[sumedge].next=head[u];
    head[u]=sumedge;
}
void addtwo(int u,int v) {
    add(u,v);
    add(v,u);
}
void dfs1(int u){
    size[u]=1;
    for(int i=head[u];i;i=edge[i].next) {
        int v=edge[i].to;
        if(v!=fa[u]) {
            fa[v]=u;
            dep[v]=dep[u]+1;
            dfs1(v);
            size[u]+=size[v];
            if(size[v]>size[son[u]]) son[u]=v;
        }
    }
}
void build(int u,int l,int r);
vector<int> line;
void dfs2(int u) {
    if(!belong[u]) {
        belong[u]=++linkcnt;
        top[belong[u]]=u;
        rnk[u]=1;
        line.push_back(0);
    }
    line.push_back(u);
    if(!son[u]) {
        lroot[belong[u]]=++treecnt;
        build(treecnt,1,rnk[u]);
        line.clear();
        return;
    }
    belong[son[u]]=belong[u];
    rnk[son[u]]=rnk[u]+1;
    dfs2(son[u]);
    for(int i=head[u];i;i=edge[i].next) {
        int v=edge[i].to;
        if(v!=son[u] && v!=fa[u]) {
            dfs2(v);
        }
    }
}
void build(int u,int l,int r) {
    tr[u].l=l;tr[u].r=r;
    if(l==r) {
        tr[u].sum=1;
        tr[u].val=num[line[l]]-num[line[l-1]];
        tr[u].sum=num[line[l]]-num[line[l-1]];
        return;
    }
    int mid=(l+r)>>1;
    tr[u].lson=++treecnt;tr[u].rson=++treecnt;
    build(tr[u].lson,l,mid);
    build(tr[u].rson,mid+1,r);
    update(u);
}
int query_tree(int u,int l,int r) {
    if(tr[u].l==l && tr[u].r==r) {
        return abs(tr[u].val);
    }
    int ls=tr[u].lson,rs=tr[u].rson;
    int mid=(tr[u].l+tr[u].r)>>1;
    if(r<=mid) {
        return query_tree(ls,l,r);
    }
    else if(l>mid) {
        return query_tree(rs,l,r);
    }
    else {
        return gcd(query_tree(ls,l,mid),query_tree(rs,mid+1,r));
    }
}
int get_sum(int u,int l,int r) {
    if(tr[u].l==l && tr[u].r==r) {
        return tr[u].sum;
    }
    int ls=tr[u].lson,rs=tr[u].rson;
    int mid=(tr[u].l+tr[u].r)>>1;
    if(r<=mid) {
        return get_sum(ls,l,r);
    }
    else if(l>mid) {
        return get_sum(rs,l,r);
    }
    else {
        return get_sum(ls,l,mid)+get_sum(rs,mid+1,r);
    }
}
void change_tree_pos(int u,int x,int d) {
    if(tr[u].l==tr[u].r) {
        tr[u].sum+=d;
        tr[u].val+=d;
        return;
    }
    int mid=(tr[u].l+tr[u].r)>>1;
    int ls=tr[u].lson,rs=tr[u].rson;
    if(x<=mid) {
        change_tree_pos(ls,x,d);
    }
    else {
        change_tree_pos(rs,x,d);
    }
    update(u);
}
int query(int a,int b) {
    int res=0;
    while(belong[a]!=belong[b]) {
        if(dep[top[belong[a]]]<dep[top[belong[b]]]) swap(a,b);
        int l=top[belong[a]],z=lroot[belong[a]];
        res=gcd(res,query_tree(z,1,rnk[a]));
        a=fa[l];
    }
    if(rnk[a]>rnk[b]) swap(a,b);
    int z=lroot[belong[a]];
    int l=get_sum(z,1,rnk[a]);
    if(rnk[a]==rnk[b]) res=gcd(res,l);
    else {
        l=gcd(l,query_tree(z,rnk[a]+1,rnk[b]));
        res=gcd(res,l);
    }
    return res;
}
void change(int a,int b,int d) {
    while(belong[a]!=belong[b]) {
        if(dep[top[belong[a]]]<dep[top[belong[b]]]) swap(a,b);
        int l=top[belong[a]],z=lroot[belong[a]];
        change_tree_pos(z,1,d);
        if(rnk[a]+1<=tr[z].r) {
            change_tree_pos(z,rnk[a]+1,-d);
        }
        a=fa[l];
    }
    if(rnk[a]>rnk[b]) swap(a,b);
    int z=lroot[belong[a]];
    change_tree_pos(z,rnk[a],d);
    if(rnk[b]+1<=tr[z].r) {
        change_tree_pos(z,rnk[b]+1,-d);
    }
}
void prepare() {
    scanf("%d",&n);
    int u,v;
    xiaosiji(i,1,n) {
        scanf("%d%d",&u,&v);
        ++u;++v;
        addtwo(u,v);
    }
    siji(i,1,n) {
        scanf("%d",&num[i]);
    }
    dep[1]=1;
    dfs1(1);dfs2(1);
}
void solve() {
    prepare();
    scanf("%d",&m);
    char s[5];
    int a,b,d;
    siji(i,1,m) {
        scanf("%s",s+1);
        if(s[1]=='F') {
            scanf("%d%d",&a,&b);
            ++a,++b;
            printf("%d\n",query(a,b));
        }
        else {
            scanf("%d%d%d",&a,&b,&d);
            ++a,++b;
            change(a,b,d);
        }
    }
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    solve();
    return 0; 
}