【NOIP模拟】資料結構

題目：資料結構

解析：

       線段樹

代碼：

#include <bits/stdc++.h>
using namespace std;

const int inf=1e9;
const int Max=500005;
int n,m,flag;
int num[Max],add[Max<<2];
typedef pair<int,int> pii;
pii tree[Max<<2];

inline int get_int()
{
	int x=0,f=1;
	char c;
	for(c=getchar();(!isdigit(c))&&(c!='-');c=getchar());
	if(c=='-') f=-1,c=getchar();
	for(;isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+c-'0';
	return x*f;
}
inline void print(int x)
{
	if(x>9) print(x/10);
	putchar('0'+x%10);
}

inline int max(int x,int y){return x<y?y:x;}
inline int min(int x,int y){return x<y?x:y;}
inline void pushnow(int root,int x)
{
	tree[root].first=max(tree[root].first,x);
	add[root]=max(add[root],x);
}
inline void pushdown(int root)
{
	if(!add[root]) return;
	pushnow(root<<1,add[root]),pushnow(root<<1|1,add[root]);
	add[root]=0;
}
inline void update(int root){tree[root]=min(tree[root<<1],tree[root<<1|1]);}
inline void build(int root,int l,int r)
{
	if(l==r){tree[root]=pii(num[l],l);return;}
	int mid=(l+r)>>1;
	build(root<<1,l,mid),build(root<<1|1,mid+1,r);
	update(root);
}
inline void change(int root,int l,int r,int L,int R,int x)
{
	if(L<=l&&R>=r) return pushnow(root,x);
	int mid=(l+r)>>1;
	pushdown(root);
	if(L<=mid) change(root<<1,l,mid,L,R,x);
	if(R>mid) change(root<<1|1,mid+1,r,L,R,x);
	update(root);
}
inline void modify(int root,int l,int r,int pos,int x)
{
	if(l==r&&l==pos) {tree[root]=pii(x,l);return;}
	int mid=(l+r)>>1;
	pushdown(root);
	(pos<=mid) ? modify(root<<1,l,mid,pos,x) : modify(root<<1|1,mid+1,r,pos,x);
	update(root);
}
inline pii Q(int root,int l,int r,int L,int R)
{
	if(L<=l&&R>=r) return tree[root];
	int mid=(l+r)>>1;
	pushdown(root);
	if(R<=mid) return Q(root<<1,l,mid,L,R);
	else if(L>mid) return Q(root<<1|1,mid+1,r,L,R);
	else return min(Q(root<<1,l,mid,L,R),Q(root<<1|1,mid+1,r,L,R));
}

int main()
{
	n=get_int();
	for(int i=1;i<=n;i++) num[i]=get_int();
	build(1,1,n);
	m=get_int();
	while(m--)
	{
	  int tag=get_int(),l=get_int(),r=get_int(),x=get_int();
	  if(tag==1) change(1,1,n,l,r,x);
	  else
	  {
	  	flag=0;
	  	int k=get_int();
	  	vector<pii>q;
	  	for(int i=1;i<=k;i++)
	  	{
	  	  pii mn=Q(1,1,n,l,r);
	  	  if(mn.first>=x) {flag=1;break;}
	  	  q.push_back(mn);modify(1,1,n,mn.second,inf);
	  	}
	  	if(flag) puts("-1");
	  	else {for(int i=0;i<q.size();i++) print(q[i].first),putchar(' ');putchar('\n');}
	  	for(int i=0;i<q.size();i++) modify(1,1,n,q[i].second,q[i].first);
	  }
	}
	return 0;
}