線段樹：
圖中的元素【a，b】表示該節點存儲的值是在a到b內的結果（最大值或者和）。其根節點為c的話，其下面兩個子樹節點的序號為 c*2 和 c*2+1
區間最大值
題目：
<喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KClByb2JsZW0gRGVzY3JpcHRpb24KCrrctuDRp9CjwffQ0NK71taxyL3PtcTPsLnfoaPAz8qmw8e63M+yu7bRr87Ko6y008SzxLO1vcSzxLO1sdbQo6y31sr91+6437XEyse24MnZoaM8YnI+CtXiyMO63Lbg0afJ+rrct7S40KGjPGJyPgo8YnI+CrK7udzE48+ysrvPsru2o6zP1tTa0OjSqsTj1/a1xMrHo6y+zcrHsLTV1cDPyqa1xNKqx/OjrNC00ru49rPM0PKjrMSjxOLAz8qmtcTRr87KoaO1sci7o6zAz8qm09DKsbry0OjSqrj80MLEs867zazRp7XEs8m8qKGjCgogCjxicj4KCklucHV0CgqxvszixL+w/LqstuDX6bLiytSjrMfrtKbA7bW9zsS8/r3hyvihozxicj4K1NrDv7j2suLK1LXEtdrSu9DQo6zT0MG9uPbV/dX7yv0gTiC6zSBNICggMDxOPD0yMDAwMDAsMDxNPDUwMDAgKaOst9ax8LT6se3Rp8n6tcTK/cS/us2y2df3tcTK/cS/oaM8YnI+CtGnyfpJRLHgusW31rHwtNMxseC1vU6hozxicj4Ktdq2/tDQsPy6rE649tX7yv2jrLT6se3V4k649tGnyfq1xLP1yryzybyoo6zG5NbQtdppuPbK/bT6se1JRM6qabXE0afJ+rXEs8m8qKGjPGJyPgq908/CwLTT0E3Q0KGjw7/Su9DQ09DSu7j219a3+yBDICjWu8ih"Q'或'U') ，和兩個正整數A，B。
當C為'Q'的時候，表示這是一條詢問操作，它詢問ID從A到B(包括A,B)的學生當中，成績最高的是多少。
當C為'U'的時候，表示這是一條更新操作，要求把ID為A的學生的成績更改為B。
Output
對於每一次詢問操作，在一行裡面輸出最高成績。
Sample Input
5 6
1 2 3 4 5
Q 1 5
U 3 6
Q 3 4
Q 4 5
U 2 9
Q 1 5
Sample Output
5
6
5
9
---改自 飄過的小牛
#include
#include
#include
#include
using namespace std;
#define lson l, m, root << 1
#define rson m + 1, r, root << 1 | 1
const int N = 200010;
int segtree[N << 1 + 10]; //開2倍
void PushUp(int root) //節點保存區間最大值
{
segtree[root] = max(segtree[root << 1], segtree[root << 1 | 1]);
}
void Build_Tree(int l, int r, int root)
{
if(l == r)
{
scanf("%d", &segtree[root]);
//cout<> 1;
Build_Tree(lson);
Build_Tree(rson);
PushUp(root);
}
void Update(int pos, int data, int l, int r, int root)
{
if(l == r)
{
segtree[root] = data;
return ;
}
int m = (l + r) >> 1;
if(pos <= m)
Update(pos, data, lson);
else
Update(pos, data, rson);
PushUp(root);
}
int Query(int L, int R, int l, int r, int root)
{
int sum = -9999999;
if(L <= l && r <= R)
return segtree[root];
int m = (l + r) >> 1;
if(L <= m)
sum = max(sum, Query(L, R, lson));
if(R > m)
sum = max(sum, Query(L, R, rson));
return sum;
}
int main()
{
int num, que;
char ope;
int a, b;
while(scanf("%d%d", &num, &que) != EOF)
{
Build_Tree(1, num, 1);
//for(int i=0;i
題目：區間求和
士兵殺敵（二）
時間限制：1000 ms | 內存限制：65535 KB
難度：5
-
描述
-
南將軍手下有N個士兵，分別編號1到N，這些士兵的殺敵數都是已知的。
小工是南將軍手下的軍師，南將軍經常想知道第m號到第n號士兵的總殺敵數，請你幫助小工來回答南將軍吧。
南將軍的某次詢問之後士兵i可能又殺敵q人，之後南將軍再詢問的時候，需要考慮到新增的殺敵數。
-
輸入
- 只有一組測試數據
第一行是兩個整數N,M，其中N表示士兵的個數(1
隨後的一行是N個整數，ai表示第i號士兵殺敵數目。(0<=ai<=100)
隨後的M行每行是一條指令，這條指令包含了一個字符串和兩個整數，首先是一個字符串，如果是字符串QUERY則表示南將軍進行了查詢操作，後面的兩個整數m,n，表示查詢的起始與終止士兵編號；如果是字符串ADD則後面跟的兩個整數I,A(1<=I<=N,1<=A<=100),表示第I個士兵新增殺敵數為A.
-
輸出
- 對於每次查詢，輸出一個整數R表示第m號士兵到第n號士兵的總殺敵數，每組輸出占一行
-
樣例輸入
-
5 6
1 2 3 4 5
QUERY 1 3
ADD 1 2
QUERY 1 3
ADD 2 3
QUERY 1 2
QUERY 1 5
-
樣例輸出
-
6
8
8
20
--
#include
int sum[3000000];
void build(int b, int e, int index)
{
if(b==e)
{
scanf("%d", &sum[index]);
return;
}
int mid = (b+e)/2, lchild=index<<1 ,rchild=lchild|1;
build(b, mid, lchild);
build(mid+1, e, rchild);
sum[index] = sum[lchild] + sum[rchild];
}
int query(int qb, int qe, int b, int e, int index)
{
if(qb<=b && e<=qe)
return sum[index];
int mid = (b+e)/2, lchild=index<<1 ,rchild=lchild|1, lr=0, rr=0;
if(qb<=mid)lr = query(qb, qe, b, mid, lchild);
if(qe>mid) rr = query(qb, qe, mid+1, e,rchild);
return lr+rr;
}
void update(int b, int e, int node, int num, int index)
{
if(b==e && e==node)
{
sum[index]+=num;
return;
}
int mid = (b+e)/2, lchild=index<<1 ,rchild=lchild|1;
if(node<=mid)update(b, mid, node, num, lchild);
else update(mid+1, e, node, num, rchild);
sum[index] += num;
}
int main()
{
int n, k, b, e;
char str[10];
scanf("%d %d", &n, &k);
build(1, n, 1);
for(int i=0; i
題目：藍橋杯練習題目-綜合了區間最大和區間和
算法訓練 操作格子
時間限制：1.0s 內存限制：256.0MB
問題描述
有n個格子，從左到右放成一排，編號為1-n。
共有m次操作，有3種操作類型：
1.修改一個格子的權值，
2.求連續一段格子權值和，
3.求連續一段格子的最大值。
對於每個2、3操作輸出你所求出的結果。
輸入格式
第一行2個整數n，m。
接下來一行n個整數表示n個格子的初始權值。
接下來m行，每行3個整數p,x,y，p表示操作類型，p=1時表示修改格子x的權值為y，p=2時表示求區間[x,y]內格子權值和，p=3時表示求區間[x,y]內格子最大的權值。
輸出格式
有若干行，行數等於p=2或3的操作總數。
每行1個整數，對應了每個p=2或3操作的結果。
樣例輸入
4 3
1 2 3 4
2 1 3
1 4 3
3 1 4
樣例輸出
6
3
數據規模與約定
對於20%的數據n <= 100，m <= 200。
對於50%的數據n <= 5000，m <= 5000。
對於100%的數據1 <= n <= 100000，m <= 100000，0 <= 格子權值 <= 10000。
#include
#include
using namespace std;
const int MAX = 100110;
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
int sum[MAX << 2], segs[MAX << 2], maxv[MAX << 2];//區間和-區間值-區間最大
inline void push_up(int rt){
sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
maxv[rt] = max(maxv[rt << 1], maxv[rt << 1 | 1]);
}
void build_up(int l, int r, int rt){
if(l == r){
scanf("%d", &segs[rt]);
sum[rt] = segs[rt];
maxv[rt] = segs[rt];
return;
}
int m = (l + r) >> 1;
build_up(lson);
build_up(rson);
push_up(rt);
}
void update(int l, int r, int rt, int p, int v){
if(l == r){
segs[rt] = v;
maxv[rt] = v;
sum[rt] = v;
return;
}
int m = (l + r) >> 1;
if(p <= m)update(lson, p, v);
else update(rson, p, v);
push_up(rt);
}
int query_sum(int L, int R, int l, int r, int rt){
if(L <= l && r <= R){
return sum[rt];
}
int ret = 0;
int m = (l + r) >> 1;
if(L <= m)ret += query_sum(L, R, lson);
if(R > m)ret += query_sum(L, R, rson);
return ret;
}
int query_max(int L, int R, int l, int r, int rt){
if(L <= l && r <= R){
return maxv[rt];
}
int ret = -1;
int m = (l + r) >> 1;
if(L <= m)ret = max(ret, query_max(L, R, lson));
if(R > m)ret = max(ret, query_max(L, R, rson));
return ret;
}
int main(){
int n, m;
cin >> n >> m;
build_up(1, n, 1);
while(m--){
int p, x, y;
scanf("%d%d%d", &p, &x, &y);
if(p == 1){
update(1, n, 1, x, y);
}else if(p == 2){
printf("%d\n", query_sum(x, y, 1, n, 1));
}else{
printf("%d\n", query_max(x, y, 1, n, 1));
}
}
return 0;
}
題目：
摻雜幾何知識
Crane
Time Limit: 2000MS
Memory Limit: 65536K
Total Submissions: 3012
Accepted: 806
Special Judge
Description
ACM has bought a new crane (crane -- je?áb) . The crane consists of n segments of various lengths, connected by flexible joints. The end of the i-th segment is joined to the beginning of the i + 1-th one, for 1 ≤ i < n. The beginning of the first segment is
fixed at point with coordinates (0, 0) and its end at point with coordinates (0, w), where w is the length of the first segment. All of the segments lie always in one plane, and the joints allow arbitrary rotation in that plane. After series of unpleasant
accidents, it was decided that software that controls the crane must contain a piece of code that constantly checks the position of the end of crane, and stops the crane if a collision should happen.
Your task is to write a part of this software that determines the position of the end of the n-th segment after each command. The state of the crane is determined by the angles between consecutive segments. Initially, all of the angles are straight, i.e., 180o.
The operator issues commands that change the angle in exactly one joint.
Input
The input consists of several instances, separated by single empty lines.
The first line of each instance consists of two integers 1 ≤ n ≤10 000 and c 0 separated by a single space -- the number of segments of the crane and the number of commands. The second line consists of n integers l1,..., ln (1 li 100) separated by single spaces.
The length of the i-th segment of the crane is li. The following c lines specify the commands of the operator. Each line describing the command consists of two integers s and a (1 ≤ s < n, 0 ≤ a ≤ 359) separated by a single space -- the order to change the
angle between the s-th and the s + 1-th segment to a degrees (the angle is measured counterclockwise from the s-th to the s + 1-th segment).
Output
The output for each instance consists of c lines. The i-th of the lines consists of two rational numbers x and y separated by a single space -- the coordinates of the end of the n-th segment after the i-th command, rounded to two digits after the decimal point.
The outputs for each two consecutive instances must be separated by a single empty line.
Sample Input
2 1
10 5
1 90
3 2
5 5 5
1 270
2 90
Sample Output
5.00 10.00
-10.00 5.00
-5.00 10.00
#include
#include
#include
#include
using namespace std;
#define lson i<<1
#define rson i<<1|1
#define lc l,mid,i<<1
#define rc mid+1,r,i<<1|1
const int L = 100000+10;
const double pi = acos(-1.0);
struct node
{
double x,y;
int deg;
int flag;
} a[L<<2];
double set(int x)
{
return x*pi/180;
}
void work(int i,int deg)//求新坐標公式
{
double r = set(deg);
double x = a[i].x;
double y = a[i].y;
a[i].x = x*cos(r)-y*sin(r);
a[i].y = x*sin(r)+y*cos(r);
a[i].deg = (a[i].deg+deg)%360;
}
void pushup(int i)
{
a[i].x = a[lson].x+a[rson].x;
a[i].y = a[lson].y+a[rson].y;
}
void pushdown(int i)
{
if(a[i].flag)
{
work(lson,a[i].flag);
work(rson,a[i].flag);
a[lson].flag+=a[i].flag;
a[rson].flag+=a[i].flag;
a[i].flag = 0;
}
}
void init(int l,int r,int i)
{
a[i].x = a[i].y = 0;
a[i].flag = a[i].deg = 0;
if(l == r)
{
scanf("%lf",&a[i].y);
return;
}
int mid = (l+r)>>1;
init(lc);
init(rc);
pushup(i);
}
void insert(int l,int r,int i,int L,int R,int z)
{
if(L<=l && r<=R)
{
work(i,z);
a[i].flag+=z;
return ;
}
pushdown(i);
int mid = (l+r)>>1;
if(L<=mid)
insert(lc,L,R,z);
if(R>mid)
insert(rc,L,R,z);
pushup(i);
}
int query(int l,int r,int i,int x)
{
if(l == r)
return a[i].deg;
pushdown(i);
int mid = (l+r)>>1;
if(x<=mid)
return query(lc,x);
else
return query(rc,x);
}
int main()
{
int n,m,x,y,flag = 1,i,j;
while(~scanf("%d%d",&n,&m))
{
init(0,n-1,1);
if(!flag)
printf("\n");
flag = 0;
while(m--)
{
scanf("%d%d",&x,&y);
int deg;
deg = query(0,n-1,1,x-1)+180+y-query(0,n-1,1,x);
//由於題目是逆時針轉的，該計算是順時針，要加上180度,將後面的棒看成依然在Y軸，所以要減去後一個的角度
insert(0,n-1,1,x,n-1,deg);
printf("%.2f %.2f\n",a[1].x,a[1].y);
}
}
return 0;
}
