题目描述

小明对某些事物十分好奇，不过这次他却十分格式化地和你说话： 给你t个组，每组有两个数x，y。  一共q次查询，给你一个flag，与l，r 当flag=1时，每次查询区间[l,r] 这些组中一个最大的x，  当flag=0时，每次查询区间[l,r] 这些组中一个最大的y。

输入格式

输入第一行有两个整数t,q分别表示组数，与查询次数。  接下来t行，每行三个整数Ci，xi，yi，分别表示组的类别，x，y值。  接下来q行，每行三个整数fi，li，ri，f如题目描述中所述，表示查询类型，l，r表示查询区间，数据保证r>l，f只为1与0。

输出格式

输出共q行，每行一个整数，表示所询问的答案。

样例输入

3 2 1 4 9 4 5 20 5 30 5 1 2 3 0 1 2

样例输出

30 20

提示

对于30%的数据t≤100000,q≤100000  对于60%的数据t≤100000,q≤1000000  对于100%的数据t≤1000000,q≤1000000  所有数据均为非负整数，且都不大于2147483647（int范围内）。

线段树裸题

#include <bits/stdc++.h> using namespace std; const int maxn=1000000+6; int n,a[maxn],b[maxn],q; struct node { int l,r; int ansx,ansy,lazy; void update(int x) { lazy+=x; } }tree[maxn*4]; void push_up(int x) { tree[x].ansx=max(tree[x<<1].ansx,tree[x<<1|1].ansx); tree[x].ansy=max(tree[x<<1].ansy,tree[x<<1|1].ansy); } void push_down(int x) { int lazyval=tree[x].lazy; if(lazyval){ tree[x<<1].update(lazyval); tree[x<<1|1].update(lazyval); tree[x].lazy=0; } } void build(int x,int l,int r) { tree[x].l=l,tree[x].r=r; tree[x].ansx=tree[x].ansy=tree[x].lazy=0; if(l==r){ tree[x].ansx=a[l]; tree[x].ansy=b[l]; }else{ int mid=(l+r)/2; build(x<<1,l,mid); build(x<<1|1,mid+1,r); push_up(x); } } /* void update(int x,int l,int r,long long val) { int L=tree[x].l,R=tree[x].r; if(l<=L&&R<=r) tree[x].update(val); else{ push_down(x); int mid=(L+R)/2; if(mid>=l)update(x<<1,l,r,val); if(r>mid)update(x<<1|1,l,r,val); push_up(x); } } */ int query_x(int x,int l,int r) { int L=tree[x].l,R=tree[x].r; if(l<=L&&R<=r) return tree[x].ansx; else{ push_down(x); int ans=0; int mid=(L+R)/2; if(mid>=l)ans=max(ans,query_x(x<<1,l,r)); if(r>mid)ans=max(ans,query_x(x<<1|1,l,r)); push_up(x); return ans; } } int query_y(int x,int l,int r) { int L=tree[x].l,R=tree[x].r; if(l<=L&&R<=r) return tree[x].ansy; else{ push_down(x); int ans=0; int mid=(L+R)/2; if(mid>=l)ans=max(ans,query_y(x<<1,l,r)); if(r>mid)ans=max(ans,query_y(x<<1|1,l,r)); push_up(x); return ans; } } int main() { scanf("%d%d",&n,&q); int opt; for(int i=1;i<=n;i++){ scanf("%d%d%d",&opt,&a[i],&b[i]); } build(1,1,n); // scanf("%d",&q); for(int i=1;i<=q;i++){ int flag,l,r; scanf("%d%d%d",&flag,&l,&r); if(flag==1) printf("%d\n",query_x(1,l,r)); else printf("%d\n",query_y(1,l,r)); } return 0; }