建议加强数据
查看原帖
建议加强数据
541069
SuperCowHorse楼主2024/9/11 18:43

不是这 O(nm)O(nm) 循环展开过了。。。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
int n,Q;ll a[maxn];
inline ll read(){
	ll s=0;char c;
	ll f=1;
	for(c=getchar_unlocked();(c<'0'||c>'9')&&c!='-';c=getchar_unlocked());
	if(c=='-') f=-1;
	else s=c-'0';
	for(c=getchar_unlocked();c>='0'&&c<='9';s=s*10+c-'0',c=getchar_unlocked());
	return s*f;
}
signed main(){
	n=read();Q=read();
	for(ll l,r;Q;--Q){
		char op[3];scanf("%s",op);l=read();r=read();--r;
		if(op[0]=='C'){
			ll v;v=read();
			int i;
			for(i=l;i+14<=r;i+=15){
				a[i]+=v;a[i+1]+=v;a[i+2]+=v;a[i+3]+=v;a[i+4]+=v;a[i+5]+=v;a[i+6]+=v;a[i+7]+=v;a[i+8]+=v;a[i+9]+=v;a[i+10]+=v;a[i+11]+=v;a[i+12]+=v;a[i+13]+=v;a[i+14]+=v;
			}
			for(;i<=r;++i){
				a[i]+=v;
			}
		}
		else{
			ll u=0,v;ll s=r-l+1;
			for(ll i=l;i<=r;++i){
				u+=(1ll*(i-l+1)*(r-i+1))*a[i];
			}
			v=s*(s+1)/2;
			if(u==0){
				printf("0/1\n");
				continue;
			}
			ll g=__gcd(u,v);
			printf("%lld/%lld\n",u/g,v/g);
		}
	}
	return 0;
}
2024/9/11 18:43
加载中...