线。段。树--树状数组-主席树

敌兵布阵

C国的死对头A国这段时间正在进行军事演习，所以C国间谍头子Derek和他手下Tidy又开始忙乎了。

A国在海岸线沿直线布置了N个工兵营地,Derek和Tidy的任务就是要监视这些工兵营地的活动情况。

由于采取了某种先进的监测手段，所以每个工兵营地的人数C国都掌握的一清二楚,每个工兵营地的人数都有可能发生变动，可能增加或减少若干人手,但这些都逃不过C国的监视。

中央情报局要研究敌人究竟演习什么战术,所以Tidy要随时向Derek汇报某一段连续的工兵营地一共有多少人,例如Derek问:“Tidy,马上汇报第3个营地到第10个营地共有多少人!”Tidy就要马上开始计算这一段的总人数并汇报。

但敌兵营地的人数经常变动，而Derek每次询问的段都不一样，所以Tidy不得不每次都一个一个营地的去数，很快就精疲力尽了，Derek对Tidy的计算速度越来越不满:"你个死肥仔，算得这么慢，我炒你鱿鱼!”Tidy想：“你自己来算算看，这可真是一项累人的工作!我恨不得你炒我鱿鱼呢!”无奈之下，Tidy只好打电话向计算机专家Windbreaker求救,Windbreaker说：“死肥仔，叫你平时做多点acm题和看多点算法书，现在尝到苦果了吧!”Tidy说："我知错了。

。

。

"但Windbreaker已经挂掉电话了。

Tidy很苦恼，这么算他真的会崩溃的，聪明的读者，你能写个程序帮他完成这项工作吗？不过如果你的程序效率不够高的话，Tidy还是会受到Derek的责骂的.

Input

第一行一个整数T，表示有T组数据。

每组数据第一行一个正整数N（N<=50000）,表示敌人有N个工兵营地，接下来有N个正整数,第i个正整数ai代表第i个工兵营地里开始时有ai个人（1<=ai<=50）。

接下来每行有一条命令，命令有4种形式：
(1) Add i j,i和j为正整数,表示第i个营地增加j个人（j不超过30）
(2)Sub i j ,i和j为正整数,表示第i个营地减少j个人（j不超过30）;
(3)Query i j ,i和j为正整数,i<=j，表示询问第i到第j个营地的总人数;
(4)End 表示结束，这条命令在每组数据最后出现;
每组数据最多有40000条命令

Output

对第i组数据,首先输出“Case i:”和回车,
对于每个Query询问，输出一个整数并回车,表示询问的段中的总人数,这个数保持在int以内。

Sample

1 
10 
1 2 3 4 5 6 7 8 9 10 
Query 1 3 
Add 3 6 
Query 2 7 
Sub 10 2 
Add 6 3 
Query 3 10 
End 

Case 1: 
6 
33 
59

下面代码输出格式可能有问题

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

给你一个长为n的序列，有m个 *** 作，全局加，或者查询区间最大子段和。

第一行两个数n,m
之后一行n个数表示这个序列
之后m行，每行一个 *** 作
1 x : 所有数都加上x
2 l r : 查询区间[l,r]内的最大子段和（可以不选数）

对于每个2种类 *** 作，输出一行一个数表示答案

示例1

5 7 -10 -3 -2 -4 -5 2 2 4 1 5 2 2 4 1 3 2 1 5 1 2 2 3 5

5 7
-10 -3 -2 -4 -5
2 2 4
1 5
2 2 4
1 3
2 1 5
1 2
2 3 5

0 6 18 19

0
6
18
19

1 <= n <= 300000
1 <= m <= 600000
序列中的数绝对值<= 2000000000
1操作中的x的绝对值<= 50000000

考点，区间加法性质，区间 *** 作，区间查询---点查询就不要记了，直接用退化版的区间查询

给出一个序列，你的任务是求每次 *** 作之后序列中 （a[j]-a[i]）/（j-i）【1<=i

*** 作次数有Q次，每次 *** 作需要将位子p处的数字变成y.

本题包含多组输入，每组输入第一行一个数字n，表示序列的长度。


然后接下来一行输入n个数，表示原先序列的样子。


再接下来一行一个数字Q，表示需要进行的 *** 作的次数。


最后Q行每行两个元素p，y，表示本 *** 作需要将位子p处的数字变成y.
数据范围：
3<=n<=200000
1<=Q<=200000
-1000000000<=a[i]<=1000000000

每组数据输出Q行，每行输出一个浮点数，保留两位小数，表示所求的最大值。

示例1

5 2 4 6 8 10 2 2 5 4 9

5
2 4 6 8 10
2
2 5
4 9

3.00 3.00

3.00
3.00

第一次 *** 作之后的序列变成：2 5 6 8 10
第二次 *** 作之后的序列变成：2 5 6 9 10

输入只有整形

分析：a[j]-a[i]）/（j-i）【1<=i

不符合区间加法

转化1：求最大值，而最大值一定是相邻两个元素的差求出来的

直观可以看出来，最大值就是相邻两个数求得的；

几何上看，求得像是两点之间的斜率，可知相邻两点之间的最大

怎么由输入数据得到线段树的节点数据，注意改一个数组元素，可能有两个节点信息改变线段树单点修改 

#include 
#include 
#include 
using namespace std;
const int maxn = 200000;
int a[maxn + 10];
int b[maxn + 10];
struct SegMent {
	int l, r;
	int val;
}que[maxn * 4];
void PushUp(int s) {
	que[s].val = max(que[s << 1].val, que[s << 1 | 1].val);
	return;
}
void buildT(int L, int R, int s = 1) {
	que[s].l = L;
	que[s].r = R;
	if (R == L) {
		que[s].val = a[L];
		return;
	}
	int mid = (L + R) / 2;
	buildT(L, mid, s << 1);
	buildT(mid + 1, R, s << 1 | 1);
	que[s].val = max(que[s << 1].val, que[s << 1 | 1].val);
	//PushUp(s);
	return;
}
void update(int k, int y, int s = 1) {
	if (que[s].l == que[s].r) {
		if (que[s].l == k)
			que[s].val = y;
		return;
	}
	int mid = (que[s].l + que[s].r) / 2;
	if (k <= mid)update(k, y, s << 1);
	else
		update(k, y, s << 1 | 1);
	que[s].val = max(que[s << 1].val, que[s << 1 | 1].val);
	//PushUp(s);
}
int query(int s = 1) {
	if (que[s].l == que[s].r) {
		return que[s].val;
	}
	return max(query(s * 2), query(s * 2 + 1));
}
int main() {
	int n, q;

	while (scanf("%d", &n) != EOF) {
		scanf("%d", &b[1]);
		for (int i = 2; i <= n; i++)
		{
			scanf("%d", &b[i]);
			a[i - 1] = b[i] - b[i - 1];
		}
		scanf("%d", &q);
		buildT(1, n - 1, 1);
		for (int i = 1; i <= q; i++) {
			int p, y;
			scanf("%d%d", &p, &y);
			b[p] = y;
			if (p <= n - 1) {
				a[p] = b[p + 1] - y;
				update(p, a[p], 1);
			}
			if (p > 1) {
				a[p - 1] = y - b[p - 1];
				update(p - 1, a[p - 1], 1);
			}
			printf("%.2lf\n", 1.0 * que[1].val);
		}
	}

	return 0;
}

随机树
 

平日里写hash的时候，总有某些选手由于脸黑而导致惨遭卡模数，然后一些恶意卡模数的出题人也因此身败名裂。

为了防止被卡，我们用一种高级的随机方式来代替原来的线性随机生成，也就是所谓的随机树！

现在有一棵编号为0~n-1的有根树，其中0是树的根。

每个节点初始有一个值Ti。

现在要求支持一下两种 *** 作：

1.  给出两个正整数u和x，我们将Tu的值乘以x，我们将这种 *** 作称为SEED *** 作。

2.  给出一个正整数i，询问Si以及它一共有多少个正约数。

其中Si表示以i为根的子树所有点的权值的乘积，我们将这种 *** 作称为RAND *** 作。

容易发现，这样得到的答案还是很随机的。

（其实不是）

你需要回答每一次的询问，由于一个数的约数个数可能非常多，这个数也可以非常大，你只需要把答案对1e9+7取模就可以了。

第一行一个正整数n，表示节点个数。


接下来n-1行，每行两个正整数u和v，表示u是v的父节点。


接下来一行n个正整数，分别表示每个节点的初始权值Ti。


接下来一行一个正整数q，表示 *** 作的个数。


接下来q行，每行是以下两种情况之一：
1.  SEED u x
表示将u节点的权值乘以x。


2. RAND i
表示询问Si以及它一共有多少个正约数。

每一行两个整数，对应一个RAND *** 作，你需要输出所求的权值以及它的正约数个数，答案对于1e9+7取模即可。

示例1

8 0 1 0 2 1 3 2 4 2 5 3 6 3 7 7 3 10 8 12 14 40 15 3 RAND 1 SEED 1 13 RAND 1

8
0 1 
0 2 
1 3 
2 4 
2 5 
3 6 
3 7
7 3 10 8 12 14 40 15 
3
RAND 1
SEED 1 13
RAND 1

14400 63 187200 126

14400 63 
187200 126

对于20%的数据，1 ≤ n, q ≤ 10。

对于40%的数据，1 ≤ n, q ≤ 100。

对于60%的数据，1 ≤ n, q ≤ 2000。

对于80%的数据，1 ≤ n, q ≤ 50000。

对于100%的数据，1 ≤ n, q ≤ 100000。

另外请注意，所有读入的数一定满足1 ≤ x ≤ 109 。

同时，数据保证在任意时刻，每个点的权值不可能拥有超过13的素因子，也就是说，每个数的素因子最多只有2，3，5，7，11，13这六种可能。

线段树是处理连续区间的区间和问题

转化，求DFS序列，得出连续区间，再利用线段树求解

参考别人程序改的

#include 
#include 
#include 
#include 
#include 

复写一版

#include 
using namespace std;
typedef long long ll;
const ll mod = 1e9 +7;
const int maxn = 1e5 +10;

int n,q,cnt;
vector> connect(maxn);
//vector connect[maxn];
int in[maxn],out[maxn],value[maxn];
int prime[6] = {2,3,5,7,11,13};
int queryRes[15];
mapid;
struct SegNode{
    int L,R;
    int sum[6];
}que[maxn<<2];
void Dfs(int u){
    in[u]  = ++cnt;
    id[cnt] = u;
    int size = connect[u].size();
    for(int i = 0;i < size;i++)
        Dfs(connect[u][i]);
    out[u]  = cnt;
}
//a^b mod
ll qpow(int a,int n){
    ll ans = 1;
    while(n>0){
        if(n&1){
            ans = a*ans%mod;
        }
        a = (ll)a*a%mod;
        n>>=1;
    }
    return ans;
}
void build(int L,int R,int s){
    que[s].L = L;
    que[s].R = R;
    memset(que[s].sum,0,6*sizeof(int));
    if(L == R){
        for(int i = 0;i < 6;i++){
            while(value[id[L]]%prime[i] == 0)
            {
                que[s].sum[i]++;
                value[id[L]]/=prime[i];
            }
        }
        return;
    }
    int mid = (L+R)/2;
    build(L,mid,s<<1);
    build(mid+1,R,s<<1|1);
    for(int i = 0;i < 6;i++)
        que[s].sum[i] = que[s<<1].sum[i]+que[s<<1|1].sum[i];
    return;
}

void update(int k,int c,int s){
    if(que[s].L == que[s].R){
        for(int i = 0;i < 6;i++){
            while(c%prime[i] == 0)
            {
                que[s].sum[i]++;
                c /= prime[i];
            }
        }
        return;
    }
    int mid = (que[s].L+que[s].R)/2;
    if(k <= mid)update(k,c,s<<1);
    else update(k,c,s<<1|1);
    for(int i = 0;i < 6;i++)
        que[s].sum[i] = que[s<<1].sum[i]+que[s<<1|1].sum[i];
    return;
}
void query(int L,int R,int s){
    if(que[s].L>=L&&que[s].R<=R){
        for(int i = 0;i < 6;i++)
            queryRes[i]+=que[s].sum[i];
        return;
    }
    int mid = (que[s].L+que[s].R)/2;
    if(mid>=L)query(L,R,s<<1);
    if(mid