WA on #6求有同样WA经历的巨佬该怎么改
查看原帖
WA on #6求有同样WA经历的巨佬该怎么改
120911
Lynkcat楼主2020/10/8 20:27

rt,代码如下

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

inline int read(){
    int x = 0; char ch = getchar(); bool positive = 1;
    for (; !isdigit(ch); ch = getchar())	if (ch == '-')	positive = 0;
    for (; isdigit(ch); ch = getchar())	x = x * 10 + ch - '0';
    return positive ? x : -x;
}
inline void write(int a){
    if(a>=10)write(a/10);
    putchar('0'+a%10);
}
inline void writesp(int a){
    if(a>=10)write(a/10);
    putchar('0'+a%10);
    printf(" ");
}
inline void writeln(int a){
    if(a<0){
    	a=-a; putchar('-');
    }
    write(a); puts("");
}

int ret,cnt,l1,r1,n,K,mn,lg[100005],st[18][100005],Tag[20000000],Ans[20000000],Lson[20000000],Rson[20000000],mid,k,l,r,q,val,root;

int ST_query(int l,int r)
{
	int tp=lg[r-l+1]-1;
	//cout<<"?!?!?!?!?!?!"<<l<<" "<<r<<" "<<min(st[tp][l],st[tp][r-(1<<tp)+1])<<endl;
	return min(st[tp][l],st[tp][r-(1<<tp)+1]);
}

int Query(int l,int r)
{
	l1=(l-1)/n+1,r1=(r-1)/n+1;
	//cout<<l<<" "<<r<<" "<<mn<<" nmsl"<<endl;
	if (r-l+1>=n) return mn;else
	if (l1==r1)
	{
		return ST_query((l-1)%n+1,(r-1)%n+1);
	} else
	return min(ST_query((l-1)%n+1,n),ST_query(1,(r-1)%n+1));
}
	

void push_down(int k,int l,int r)
{
	//cout<<"Push_down "<<l<<" "<<r<<" "<<Tag[k]<<endl;
	if (!Lson[k]) Lson[k]=++cnt,Ans[Lson[k]]=Query(l,l+(r-l)/2),Tag[Lson[k]]=-1;
	if (!Rson[k]) Rson[k]=++cnt,Ans[Rson[k]]=Query(l+(r-l)/2+1,r),Tag[Rson[k]]=-1;
	//cout<<"PU "<<Lson[k]<<" "<<Rson[k]<<" "<<Ans[Lson[k]]<<" "<<Ans[Rson[k]]<<endl;
	if (Tag[k]==-1) return;
	Ans[Lson[k]]=Tag[k],Tag[Lson[k]]=Tag[k];
	Ans[Rson[k]]=Tag[k],Tag[Rson[k]]=Tag[k];
	Tag[k]=-1;
}

void push_up(int k)
{
	Ans[k]=min(Ans[Lson[k]],Ans[Rson[k]]);
}

void update(int &k,int l,int r,int l1,int r1,int val)
{
	if (!k) 
	{
	    k=++cnt;
	    Ans[k]=Query(l,r);
	    Tag[k]=-1;
	}
	if (l>=l1&&r<=r1) 
	{
		Ans[k]=val;
		Tag[k]=val;
		return;
	}	
	push_down(k,l,r);
	mid=l+(r-l)/2;
	if (l1<=mid) update(Lson[k],l,mid,l1,r1,val);
	if (r1>mid) update(Rson[k],mid+1,r,l1,r1,val);
	push_up(k);
}

int query(int &k,int l,int r,int l1,int r1)
{
	if (!k)
	{
		k=++cnt;
		Ans[k]=Query(l,r);
		Tag[k]=-1;
	}
	if (l>=l1&&r<=r1) 
	{
	  return Ans[k];}
	push_down(k,l,r);
	int mid=l+(r-l)/2,ret=INT_MAX;
	if (l1<=mid) ret=min(ret,query(Lson[k],l,mid,l1,r1));
	if (r1>mid) ret=min(ret,query(Rson[k],mid+1,r,l1,r1));
	push_up(k);
	return ret;
}

signed main()
{
	n=read(),K=read();mn=INT_MAX;
	for (int i=1;i<=n;i++) st[0][i]=read(),lg[i]=lg[i/2]+1,mn=min(mn,st[0][i]);
	for (int i=1;i<=lg[n];i++)
	  for (int j=1;j+(1<<i)-1<=n;j++)
	    st[i][j]=min(st[i-1][j],st[i-1][j+(1<<i-1)]);
	//cout<<"nmsl"<<endl;
	q=read();
	for (int i=1;i<=q;i++)
	{
		k=read(),l=read(),r=read();
		if (k==1)
		{
			val=read();
			update(root,1,n*K,l,r,val);
		} else writeln(query(root,1,n*K,l,r));
	}
	//cout<<"???"<<Query(1,2)<<" "<<st[1][1]<<endl;
	return 0;
}

2020/10/8 20:27
加载中...