Segment TreeProblem Description:
A contest is not integrity without problems about data structure.
There is an array a[1],a[2],…,a[n]. And q questions of the following 4 types:Input
The first line contains a integer T(no more than 5) which represents the number of test cases.
For each test case, the first line contains 2 integers n,q (1≤n,q≤200000).
The second line contains n integers a1,a2,…,an which indicates the initial values of the array (|ai|≤).
Each of the following q lines contains an integer t which denotes the type of i-th question. If t=1,2,3, 3 integers l,r,c follows. If t=4, 2 integers l,r follows. (1≤ti≤4,1≤li≤ri≤n)
If t=1, |ci|≤2000;
If t=2,3, |ci|≤10^9.
Output
For each question of type 4, output two integers denote the minimum and the maximum.
Sample Input
11 114 1 1
Sample Output
1 1
题意：
给出一个数组，分别有4种操作
1 l r c：l~r区间的值改为c
2 l r c：l~r区间内所有比c大的值变为c
3 l r c：l~r区间内所有比c小的值变为c
4 l r：查询区间内最小与最大的数字
思路：
题目都告诉你要用线段树了，但是有一点要注意，这题开始用lld输入是WA，，改成I64D才AC
#include<stdio.h>#define LL long longconst int N = 200100;const LL INF = 9999999999999;struct Tree{LL maxt,mint,add;} node[N*3];LL max(LL a,LL b){return a>b?a:b;}LL min(LL a,LL b){return a>b?b:a;}void pushUP(int k){node[k].maxt=max(node[k<<1].maxt,node[k<<1|1].maxt);node[k].mint=min(node[k<<1].mint,node[k<<1|1].mint);}void pushDown(int k){if(node[k].add){node[k<<1].add+=node[k].add;node[k<<1].maxt+=node[k].add;node[k<<1].mint+=node[k].add;node[k<<1|1].add+=node[k].add;node[k<<1|1].maxt+=node[k].add;node[k<<1|1].mint+=node[k].add;node[k].add=0;}node[k<<1].maxt=min(node[k<<1].maxt,node[k].maxt);node[k<<1].maxt=max(node[k<<1].maxt,node[k].mint);node[k<<1].mint=max(node[k<<1].mint,node[k].mint);node[k<<1].mint=min(node[k<<1].mint,node[k].maxt);node[k<<1|1].maxt=min(node[k<<1|1].maxt,node[k].maxt);node[k<<1|1].maxt=max(node[k<<1|1].maxt,node[k].mint);node[k<<1|1].mint=max(node[k<<1|1].mint,node[k].mint);node[k<<1|1].mint=min(node[k<<1|1].mint,node[k].maxt);}void builde(int l,int r,int k){node[k].add=0;if(l==r){scanf("%I64d",&node[k].maxt);node[k].mint=node[k].maxt;return ;}int m=(l+r)>>1;builde(l,m,k<<1);builde(m+1,r,k<<1|1);pushUP(k);}int L,R;LL C;void updata1(int l,int r,int k){if(L<=l&&r<=R){node[k].add+=C;node[k].maxt+=C;node[k].mint+=C;return ;}int m=(l+r)>>1;pushDown(k);if(L<=m)updata1(l,m,k<<1);if(m<R)updata1(m+1,r,k<<1|1);pushUP(k);}void updata2(int l,int r,int k){if(L<=l&&r<=R){node[k].maxt=min(node[k].maxt,C);node[k].mint=min(node[k].mint,C);return ;}int m=(l+r)>>1;pushDown(k);if(L<=m)updata2(l,m,k<<1);if(m<R)updata2(m+1,r,k<<1|1);pushUP(k);}void updata3(int l,int r,int k){if(L<=l&&r<=R){node[k].maxt=max(node[k].maxt,C);node[k].mint=max(node[k].mint,C);return ;}int m=(l+r)>>1;pushDown(k);if(L<=m)updata3(l,m,k<<1);if(m<R)updata3(m+1,r,k<<1|1);pushUP(k);}LL maxans,minans;void query(int l,int r,int k){if(L<=l&&r<=R){maxans=max(maxans,node[k].maxt);minans=min(minans,node[k].mint);return ;}int m=(l+r)>>1;pushDown(k);if(L<=m)query(l,m,k<<1);if(m<R)query(m+1,r,k<<1|1);pushUP(k);}int main(){int T,n,q,op;scanf("%d",&T);while(T–){scanf("%d%d",&n,&q);builde(1,n,1);while(q–){scanf("%d%d%d",&op,&L,&R);if(op!=4){scanf("%I64d",&C);if(op==1)updata1(1,n,1);else if(op==2)updata2(1,n,1);else if(op==3)updata3(1,n,1);}else{minans=INF;maxans=-INF;query(1,n,1);printf("%I64d %I64d\n",minans,maxans);}}}}
影子依旧可以相亲相爱。哪一块骨骼最温暖，总能一击即中。
