不开02就WA 开完就AC?????
  • 板块P1816 忠诚
  • 楼主CRXclaire
  • 当前回复4
  • 已保存回复4
  • 发布时间2023/5/8 20:28
  • 上次更新2023/10/23 16:19:09
查看原帖
不开02就WA 开完就AC?????
606898
CRXclaire楼主2023/5/8 20:28

很怪,用线段树写的,不开02就全WA,开了就过了,为啥啊

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1000010,base=400,M=810;
int m,k,t;
ll n,res,idx,a[N];

struct node{
	int l,r;
	int minn;
}tr[N*4];

void pushup(int u){
	tr[u].minn=min(tr[u<<1].minn,tr[u<<1|1].minn);
	
}
void build(int u,int l,int r){
	tr[u]={l,r};               //这个必须写,要不然硬背吧,现在先别自己改 
	if(l==r)return;
	else {
		int mid=l+r>>1;
		build(u<<1,l,mid);
		build(u<<1|1,mid+1,r);
	}
}

void change(int u,int x,int v){
//	cout<<"******"<<endl;
	if(tr[u].l==x&&tr[u].r==x)tr[u].minn=v;
	else {
		int mid=tr[u].l+tr[u].r>>1;
		
		if(x<=mid)change(u<<1,x,v);
		else change(u<<1|1,x,v);
		pushup(u);
	}
}

ll query(int u,int l,int r){
	ll res;
//	cout<<"*"<<endl;
	if(tr[u].l>=l&&tr[u].r<=r)return  tr[u].minn;
	else {
		int mid=tr[u].l+tr[u].r>>1;
		if(l<=mid)res=query(u<<1,l,r);
		if(r>mid)res=min(res,query(u<<1|1,l,r));
	}
	return res;
//	cout<<"********"<<endl;
}
int main(){
  	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
 
   cin>>m>>n;
   build(1,1,m);
   
   for(int i=1;i<=m;i++){
   cin>>a[i];
   change(1,i,a[i]); 
  }
   
   for(int i=1;i<=n;i++){
   	ll l,r;
   	cin>>l>>r;
  // 	cout<<"((((("<<endl;
   	cout<<query(1,l,r)<<" ";
   	
   }
   return 0;  
}
2023/5/8 20:28
加载中...