分块84pts求调
查看原帖
分块84pts求调
748694
yinianxingkong楼主2023/12/16 09:49

rt,第三个点死活过不去

#include<bits/stdc++.h>
//#define int long long
using namespace std;
namespace fast_IO {
#define IOSIZE 100000
int precision=3,POW[10]={1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000};char ibuf[IOSIZE],obuf[IOSIZE],*p1=ibuf,*p2=ibuf,*p3=obuf;
#ifdef ONLINE_JUDGE
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
#endif
template<typename T>inline T read(){T s=0;int w=1;char ch;while(ch=getchar(),!isdigit(ch)&&(ch!=EOF))if(ch==45)w=-1;if(ch==EOF)return 0;while(isdigit(ch))s=s*10+ch-48,ch=getchar();return s*w;}template<typename T>inline bool read(T&s){s=0;int w=1;char ch;while(ch=getchar(),!isdigit(ch)&&(ch!=EOF))if(ch==45)w=-1;if(ch==EOF)return 0;while(isdigit(ch))s=s*10+ch-48,ch=getchar();return s*=w,1;}inline bool read(char&s){while(s=getchar(),isspace(s));return 1;}inline bool read(char*s){char ch;while(ch=getchar(),isspace(ch));if(ch==EOF)return 0;while(!isspace(ch))*s++=ch,ch=getchar();*s='\000';return 1;}template<typename T>inline void print(T x){if(x<0)putchar(45),x=-x;if(x>9)print(x/10);putchar(x%10+48);}inline void print(char x){putchar(x);}inline void print(char*x){while(*x)putchar(*x++);}inline void print(const char*x){for(int i=0;x[i];i++)putchar(x[i]);}inline bool read(std::string&s){s="";char ch;while(ch=getchar(),isspace(ch));if(ch==EOF)return 0;while(!isspace(ch))s+=ch,ch=getchar();return 1;}inline void print(std::string x){for(int i=0,n=x.size();i<n;i++)putchar(x[i]);}inline bool read(bool&b){char ch;while(ch=getchar(),isspace(ch));b=ch^48;return 1;}inline void print(bool b){putchar(b+48);}inline bool read(double&x){int a=0,b=0;char ch=getchar();bool f=0;while(ch<48||ch>57){if(ch==45)f=1;ch=getchar();}while(47<ch&&ch<58){a=(a<<1)+(a<<3)+(ch^48);ch=getchar();}if(ch!=46){x=f?-a:a;return 1;}ch=getchar();while(47<ch&&ch<58){b=(b<<1)+(b<<3)+(ch^48),ch=getchar();}x=b;while(x>1)x/=10;x=f?-a-x:a+x;return 1;}inline void print(double x){if(x<0){putchar(45),x=-x;}x=round((long double)x*POW[precision])/POW[precision],print((long long)x),putchar(46),x-=(long long)(x);for(int i=1;i<=precision;i++)x*=10,putchar(x+48),x-=(int)x;}template<typename T,typename...T1>inline int read(T& a,T1&...other){return read(a)+read(other...);}template<typename T,typename...T1>inline void print(T a,T1...other){print(a),print(other...);}struct Fast_IO{~Fast_IO(){fwrite(obuf,p3-obuf,1,stdout);}}io;template<typename T>Fast_IO& operator>>(Fast_IO&io,T&b){return read(b),io;}template<typename T>Fast_IO& operator<<(Fast_IO&io,T b){return print(b),io;}
#define cout io
#define cin io
#define endl '\n'
}using namespace fast_IO;
namespace TYX_YNXK{
	#define il inline
	#define bl bool
	#define ll long long
	#define vd void
	#define N 100005
	#define SQ 350
	#define mod 1000000007
	int n,m,opt,l,r,y,b[N],c[N];
	int len,cnt,L[SQ],R[SQ],tag[SQ],belong[N],sor[N],tmp[SQ],mxc[SQ];
	ll mul[SQ],ans,pre[N];
	ll qpow[SQ];
	il vd init(){
		len=ceil(sqrt(n));
		for(int i=1;i<=n;i++) belong[i]=(i-1)/len+1;
		cnt=belong[n];
		for(int i=1;i<=cnt;i++) L[i]=R[i-1]+1,R[i]=i*len;
		R[cnt]=n;
		for(int i=1;i<=cnt;i++){
			tag[i]=-1;
			mul[i]=1;
			tmp[i]=L[i];
			sort(sor+L[i],sor+1+R[i]);
			pre[L[i]]=sor[L[i]];
			for(int j=L[i];j<=R[i];j++){
				mul[i]=mul[i]*min(b[j],c[j])%mod;
				if(j!=L[i]) pre[j]=pre[j-1]*sor[j]%mod;
			}
			mxc[i]=c[R[i]];
		}
	}
	il vd pushdown(int k){
		if(tag[k]==-1) return;
		mul[k]=1;
		for(int i=L[k];i<=R[k];i++){
			c[i]=tag[k];
			mul[k]=mul[k]*min(c[i],b[i])%mod;
		}
		tag[k]=-1;
		mxc[k]=c[R[k]];
	}
	il vd change_a(){
		int ls=belong[l],rs=belong[r];
		if(ls==rs){
			pushdown(ls);
			for(int i=l;i<=r;i++) c[i]=y;
			mul[ls]=1;
			tmp[ls]=L[ls];
			for(int i=L[ls];i<=R[ls];i++) mul[ls]=mul[ls]*min(b[i],c[i])%mod;
			mxc[ls]=c[R[ls]];
			return;
		}
		qpow[0]=1;
		for(int i=1;i<=len;i++) qpow[i]=qpow[i-1]*y%mod;
		pushdown(ls),pushdown(rs);
		for(int i=l;i<=R[ls];i++) c[i]=y;
		for(int i=L[rs];i<=r;i++) c[i]=y;
		mul[ls]=mul[rs]=1;
		tmp[ls]=L[ls],tmp[rs]=L[rs];
		for(int i=L[ls];i<=R[ls];i++) mul[ls]=mul[ls]*min(b[i],c[i])%mod;
		for(int i=L[rs];i<=R[rs];i++) mul[rs]=mul[rs]*min(b[i],c[i])%mod;
		mxc[ls]=c[R[ls]],mxc[rs]=c[R[rs]];
		for(int i=ls+1;i<=rs-1;i++){
			tag[i]=mxc[i]=y;
			while(tmp[i]<=R[i]&&sor[tmp[i]]<y) ++tmp[i];
			if(tmp[i]==L[i]) mul[i]=1;
			else mul[i]=pre[tmp[i]-1];
			mul[i]=mul[i]*qpow[R[i]-tmp[i]+1]%mod;
		}
	}
	il vd change_b(){
		b[l]=y;
		int ls=belong[l];
		pushdown(ls);
		mul[ls]=1;
		for(int i=L[ls];i<=R[ls];i++) mul[ls]=mul[ls]*min(c[i],b[i])%mod,sor[i]=b[i];
		sort(sor+L[ls],sor+1+R[ls]);
		pre[L[ls]]=sor[L[ls]];
		for(int i=L[ls]+1;i<=R[ls];i++) pre[i]=pre[i-1]*sor[i]%mod;
		tmp[ls]=L[ls];
		mxc[ls]=c[R[ls]];
	}
	signed main(){
//		freopen("read.in","r",stdin);
//		freopen("baoli.out","w",stdout);
		cin>>n>>m;
		for(int i=1;i<=n;i++) cin>>c[i],c[i]=max(c[i],c[i-1]);
		for(int i=1;i<=n;i++) cin>>b[i],sor[i]=b[i];
		init();
		while(m--){
			cin>>opt>>l>>y;
			switch(opt){
				case 0:{
					if(c[l]<y){
						r=-1;
						for(int i=1;i<=cnt&&r==-1;i++){
							if(mxc[i]>=y){
								if(tag[i]!=-1) r=L[i]-1;
								else for(int j=L[i];j<=R[i]&&r==-1;j++){
									if(c[j]>=y) r=j-1;
								}
							}
						}
						if(r==-1) r=n;
//						cout<<"l and r: "<<l<<' '<<r<<'\n';
						change_a();
					}
					break;
				}
				case 1:{
					change_b();
					break;
				}
			}
			ans=1;
			for(int i=1;i<=cnt;i++) ans=ans*mul[i]%mod/*,cout<<mul[i]<<' '*/;
//			cout<<'\n';
			cout<<ans<<'\n';
		}
		return 0;
	}
}
signed main(){
	TYX_YNXK::main();
	return 0;
}
/*
5 5
4 0 0 2 0
1 7 5 7 4
0 4 10
0 4 13
0 5 5
0 1 11
0 1 16
*/

马蜂清奇请见谅qwq

也可以指出错在哪里,不一定需要AC代码

2023/12/16 09:49
加载中...