莫名其妙RE怎么回事
查看原帖
莫名其妙RE怎么回事
77615
OIerAlbedo楼主2021/9/5 19:13

本地测小数据都是过的

#include<bits/stdc++.h>
using namespace std;
inline long long read()
{
  long long x=0,f=1;char ch=getchar();
  while(!isdigit(ch)&&ch!='-')ch=getchar();
  if(ch=='-')f=-1,ch=getchar();
  while(isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
  return x*f;
}
long long pow(long long x,long long y,long long p)
{
    long long ans=1;
    for (;y;y>>=1,x=x*x % p)
        if (y&1) ans=ans*x % p;
    return ans;
}
long long calc(long long x,long long y)
{
	long long rit=y*(y+1)*(2*y+1)/6;
	long long lft=x*(x+1)*(2*x+1)/6;
	return rit-lft;
}
struct SegmentTree{
	long long cub,squ,sum,tag;
} tree[4001010];
char opt;
long long val,ans,tot,X,n,Q,l,r;
void pushup(long long x)
{
	tree[x].sum=tree[x*2].sum+tree[x*2+1].sum;

	tree[x].squ=tree[x*2].squ+tree[x*2+1].squ;
	
	tree[x].cub=tree[x*2].cub+tree[x*2+1].cub;
}
void pushdown(int x,int l,int r)
{
	tree[x*2].tag+=tree[x].tag;tree[x*2+1].tag+=tree[x].tag;
	int mid=(l+r)/2;
	tree[x*2].sum+=tree[x].tag*(mid-l+1);
	
	tree[x*2].squ+=tree[x].tag*((l+mid)*(mid-l+1)/2);
	
	tree[x*2].cub+=tree[x].tag*calc(l-1,mid);
	
	tree[x*2+1].sum+=tree[x].tag*(r-mid);
	
	tree[x*2+1].squ+=tree[x].tag*((mid+1+r)*(r-mid)/2);
	
	tree[x*2+1].cub+=tree[x].tag*calc(mid,r);
	tree[x].tag=0;
}
void modify(int x,int l,int r,int tl,int tr,long long val)
{
	if ((l>=tl)&&(r<=tr))
	      {
	      	tree[x].sum+=val*(r-l+1);tree[x].squ+=val*((l+r)*(r-l+1)/2);tree[x].cub+=val*calc(l-1,r);
	      	tree[x].tag+=val;
	      	return ;
		  }
	pushdown(x,l,r);
	int mid=(l+r)/2;
	if (tl<=mid) modify(x*2,l,mid,tl,tr,val);
	if (tr>mid) modify(x*2+1,mid+1,r,tl,tr,val);
	pushup(x);
}
long long query_sum(int x,int l,int r,int tl,int tr)
{
	if ((l>=tl)&&(r<=tr)) return tree[x].sum;
	pushdown(x,l,r);
	int mid=(l+r)/2;long long ans=0;
	if (tl<=mid) ans+=query_sum(x*2,l,mid,tl,tr);
	if (tr>mid) ans+=query_sum(x*2+1,mid+1,r,tl,tr);
	pushup(x);
	return ans;
}long long query_squ(int x,int l,int r,int tl,int tr)
{
	if ((l>=tl)&&(r<=tr)) return tree[x].squ;
	pushdown(x,l,r);
	int mid=(l+r)/2;long long ans=0;
	if (tl<=mid) ans+=query_squ(x*2,l,mid,tl,tr);
	if (tr>mid) ans+=query_squ(x*2+1,mid+1,r,tl,tr);
	pushup(x);
	return ans;
}
long long query_cub(int x,int l,int r,int tl,int tr)
{
	if ((l>=tl)&&(r<=tr)) return tree[x].cub;
	pushdown(x,l,r);
	int mid=(l+r)/2;long long ans=0;
	if (tl<=mid) ans+=query_cub(x*2,l,mid,tl,tr);
	if (tr>mid) ans+=query_cub(x*2+1,mid+1,r,tl,tr);
	pushup(x);
	return ans;
}
long long gcd(long long x,long long y)
{
	if (y==0) return x;
	return gcd(y,x % y);
}
int main()
{
	n=read();Q=read();
	for (;Q;Q--)
	    {
	    	scanf("%c",&opt);
	    	if (opt=='C')
	    	    {
	    	        l=read();r=read();val=read();
					if (l<=r)modify(1,1,n-1,l,r-1,val);	
				} 
			else 
			    {   
			       l=read();r=read();
			       if (l==r) 
				       {
					   puts("0/1");continue;
				}
			       ans=query_sum(1,1,n-1,l,r-1)*(-l*r+r)+query_squ(1,1,n-1,l,r-1)*(l+r-1)-query_cub(1,1,n-1,l,r-1);
			       tot=(r-l+1)*(r-l)/2;
			       X=gcd(ans,tot);
			       if (X!=0) ans/=X,tot/=X;
			       if (ans==0) puts("0/1");
			       else printf("%lld/%lld\n",ans,tot);
				}
		}
    return 0;
}

2021/9/5 19:13
加载中...