60 分部分分代码球调
查看原帖
60 分部分分代码球调
550775
rsy_楼主2024/4/30 18:06

模拟赛的时候就没过第三个大样例。

貌似是 op=3⁡\operatorname{op=3} 的时候有问题,但是感觉完全不可能有问题啊/yun。

#include <bits/stdc++.h>
#define lb(x) (x&-x)
#define L(i,j,k) for(int i=(j);i<=(k);++i)
#define R(i,j,k) for(int i=(j);i>=(k);--i)
#define int long long
#define min(a,b) ((a)<(b)?(a):(b))

using namespace std;
using i64 = long long;

typedef pair<int, int> pii;
typedef long long ll;
typedef unsigned long long ull;
void chmin(int &x, int c) {
	x = min(x, c);
}
void chmax(int &x, int c) {
	x = max(x, c);
}

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;
const int maxn = 1e6 + 10, mod = 1e9 + 7;
int n,m,a[maxn],b[maxn],c[maxn];
int opt[maxn],x[maxn],y[maxn],z[maxn];
int qmi(int a,int b){
	int res=1;
	while(b){
		if(b&1)res=1ll*res*a%mod;
		a=1ll*a*a%mod,b>>=1;
	}
	return res;
}
int C[maxn];
struct segt{
	int a,b,c,s,inv;
}tr[maxn<<2];
#define ls (u<<1)
#define rs (u<<1|1)
#define mid ((l+r)>>1)
#define lson ls,l,mid
#define rson rs,mid+1,r
inline void pushup(int u){
	tr[u].s=tr[ls].s+tr[rs].s;
	tr[u].s%=mod;
}
inline void build(int u,int l,int r){
	if(l==r){
		tr[u].a=a[l],tr[u].b=b[l];
		tr[u].inv=qmi(a[l]+b[l],mod-2);
		tr[u].c=0;
		tr[u].s=0;
		return;
	}
	build(u<<1,l,mid),build(u<<1|1,mid+1,r);
	pushup(u); 
}
inline int qy_sum(int u,int l,int r,int ql,int qr){
	if(ql<=l&&qr>=r)return tr[u].s;
	ll res=0;
	if(ql<=mid)res+=qy_sum(u<<1,l,mid,ql,qr);
	if(qr>mid)res+=qy_sum(u<<1|1,mid+1,r,ql,qr);
	return (int)(res%mod+mod)%mod;
}
void upd1(int u,int l,int r,int pos,int x){
	if(l==r){
		tr[u].c+=x;
		tr[u].c=min(tr[u].c,tr[u].a+tr[u].b);
		tr[u].s=1ll*tr[u].c*tr[u].a%mod*
			1ll*tr[u].inv%mod; 
		return;
	}
	if(pos<=mid)upd1(u<<1,l,mid,pos,x);
	if(pos>mid)upd1(u<<1|1,mid+1,r,pos,x);
	pushup(u);
}
inline void upd2(int u,int l,int r,int pos,int a,int b){
	if(l==r){
		tr[u].a+=a,tr[u].b+=b;
		tr[u].inv=qmi(tr[u].a+tr[u].b,mod-2);
		tr[u].s=1ll*tr[u].c*tr[u].a%mod*
			1ll*tr[u].inv%mod; 
		return;
	}
	if(pos<=mid)upd2(u<<1,l,mid,pos,a,b);
	if(pos>mid)upd2(u<<1|1,mid+1,r,pos,a,b);
	pushup(u); 
} 

void solve() {
	cin>>n>>m;
	L(i,1,n)cin>>a[i]>>b[i];
	L(i,1,m){
		cin>>opt[i]>>x[i]>>y[i];
		if(opt[i]^2)cin>>z[i];
	}
	build(1,1,n);
	L(i,1,m){
		if(opt[i]==1){
			L(j,x[i],y[i])upd1(1,1,n,j,z[i]);
		} 
		if(opt[i]==2){
			cout<<qy_sum(1,1,n,x[i],y[i])<<'\n'; 
		}
		if(opt[i]==3){
			upd2(1,1,n,x[i],y[i],z[i]);
		}
	}
//	if(n<=1000&&m<=1000){
//		L(i,1,m){
//			if(opt[i]==1){
//				L(j,x[i],y[i])c[j]+=z[i],chmin(c[j],a[j]+b[j]);
//			}
//			if(opt[i]==2){
//				int res=0;
//				L(j,x[i],y[i]){
//					res+=1ll*c[j]*a[j]%mod*qmi(a[j]+b[j],mod-2)%mod;
//					res%=mod;
//				}
//				cout<<res<<'\n';
//			}
//			if(opt[i]==3){
//				a[x[i]]+=y[i],b[x[i]]+=z[i];
//			}
//		}
//		return;
//	}
//	if(!F&&!F2){
//		L(i,1,m){
//			if(opt[i]==1){
//				int qy=sum(x[i])-sum(x[i]-1);
//				add(i,-qy);
//				c[x[i]]+=z[i]; 
//				chmin(c[x[i]],a[x[i]]+b[x[i]]);
//				add(x[i],c[x[i]]*a[x[i]]%mod*qmi(a[x[i]]+b[x[i]],mod-2)%mod);
//			}
//			if(opt[i]==2){
//				cout<<(sum(y[i])-sum(x[i]-1)+mod)%mod<<'\n';
//			}
//		}
//		return;
//	}
}

signed main() {
	int T = 1;
	while (T--)solve();
	return 0;
}
// 1MB
2024/4/30 18:06
加载中...