QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#216453 | #6435. Paimon Segment Tree | veg | WA | 1ms | 6216kb | C++14 | 3.5kb | 2023-10-15 18:34:51 | 2023-10-15 18:34:51 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int maxn=5e4+10;
const int mod=1e9+7;
struct Mdf
{
int l,r,x;
}b[maxn];
int a[maxn];
struct Req
{
int l,r,opt,id;
};
vector<Req> req[maxn];
int ans[maxn];
struct Node
{
int tim,sum,sumk,sum2,lenk,sum3,add,add2;
}t[maxn<<2];
void push_up(int x,int tim)
{
t[x].sum=(t[x<<1].sum+t[x<<1|1].sum)%mod;
t[x].sum2=(t[x<<1].sum2+t[x<<1|1].sum2)%mod;
t[x].sum3=(1ll*(tim-t[x<<1].tim)*t[x<<1].sum2+t[x<<1].sum3+1ll*(tim-t[x<<1|1].tim)*t[x<<1|1].sum2+t[x<<1|1].sum3)%mod;
t[x].tim=tim;
}
void build(int x,int l,int r)
{
if(l==r) return t[x].sum=(a[l]+mod)%mod,t[x].sum2=t[x].sum3=1ll*a[l]*a[l]%mod,void();
int mid=l+r>>1;
build(x<<1,l,mid);
build(x<<1|1,mid+1,r);
push_up(x,0);
}
void push_down(int x,int l,int r)
{
t[x<<1].sumk=(t[x<<1].sumk+t[x].sumk)%mod;
t[x<<1|1].sumk=(t[x<<1|1].sumk+t[x].sumk)%mod;
t[x<<1].lenk=(t[x<<1].lenk+t[x].lenk)%mod;
t[x<<1|1].lenk=(t[x<<1|1].lenk+t[x].lenk)%mod;
t[x<<1].add=(t[x<<1].add+t[x].add)%mod;
t[x<<1|1].add=(t[x<<1|1].add+t[x].add)%mod;
t[x<<1].add2=(t[x<<1].add2+t[x].add2)%mod;
t[x<<1|1].add2=(t[x<<1|1].add2+t[x].add2)%mod;
int mid=l+r>>1;
t[x<<1].sum3=(t[x<<1].sum3+1ll*t[x].sumk*t[x<<1].sum+1ll*t[x].lenk*(mid-l+1))%mod;
t[x<<1|1].sum3=(t[x<<1|1].sum3+1ll*t[x].sumk*t[x<<1|1].sum+1ll*t[x].lenk*(r-mid))%mod;
t[x<<1].sum2=(t[x<<1].sum2+2ll*t[x].add*t[x<<1].sum+1ll*t[x].add2*(mid-l+1))%mod;
t[x<<1|1].sum2=(t[x<<1|1].sum2+2ll*t[x].add*t[x<<1|1].sum+1ll*t[x].add2*(r-mid))%mod;
t[x<<1].sum=(t[x<<1].sum+1ll*t[x].add*(mid-l+1))%mod;
t[x<<1|1].sum=(t[x<<1|1].sum+1ll*t[x].add*(r-mid))%mod;
t[x<<1].tim=t[x<<1|1].tim=t[x].tim;
t[x].lenk=t[x].sumk=t[x].add=t[x].add2=0;
}
void modify(int x,int l,int r,int left,int right,int val,int tim)
{
if(l>=left&&r<=right)
{
int len=r-l+1;
t[x].sumk=(t[x].sumk+2ll*(tim-t[x].tim)*t[x].add+val*2)%mod;
t[x].lenk=(t[x].lenk+1ll*(tim-t[x].tim)*t[x].add2+1ll*val*val)%mod;
t[x].add=(t[x].add+val)%mod;
t[x].add2=(t[x].add2+1ll*val*val)%mod;
t[x].sum3=(t[x].sum3+1ll*t[x].sum2*(tim-t[x].tim)+2ll*val*t[x].sum+1ll*val*val%mod*len)%mod;
t[x].sum2=(t[x].sum2+2ll*val*t[x].sum+1ll*val*val%mod*len)%mod;
t[x].sum=(t[x].sum+1ll*val*len)%mod;
t[x].tim=tim;
printf("[%d %d %d]\n",l,r,t[x].sum3);
return;
}
int mid=l+r>>1;
push_down(x,l,r);
if(left<=mid) modify(x<<1,l,mid,left,right,val,tim);
if(right>mid) modify(x<<1|1,mid+1,r,left,right,val,tim);
push_up(x,tim);
}
int query(int x,int l,int r,int left,int right,int tim)
{
if(l>=left&&r<=right) return (1ll*(tim-t[x].tim)*t[x].sum2+t[x].sum3)%mod;
int mid=l+r>>1,ans=0;
push_down(x,l,r);
if(left<=mid) ans+=query(x<<1,l,mid,left,right,tim);
if(right>mid) ans+=query(x<<1|1,mid+1,r,left,right,tim);
return ans%mod;
}
int main()
{
int n,m,q;
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
build(1,1,n);
for(int i=1;i<=m;i++) scanf("%d%d%d",&b[i].l,&b[i].r,&b[i].x);
for(int i=1;i<=q;i++)
{
int l,r,x,y;
scanf("%d%d%d%d",&l,&r,&x,&y);
if(x) req[x-1].push_back((Req){l,r,mod-1,i});
req[y].push_back((Req){l,r,1,i});
}
for(auto v:req[0])
ans[v.id]=(ans[v.id]+1ll*v.opt*query(1,1,n,v.l,v.r,0))%mod;
for(int i=1;i<=m;i++)
{
modify(1,1,n,b[i].l,b[i].r,(b[i].x+mod)%mod,i);
if(b[i].l>1) modify(1,1,n,1,b[i].l-1,0,i);
if(b[i].r<n) modify(1,1,n,b[i].r+1,n,0,i);
printf("{%d}\n",t[1].sum3);
for(auto v:req[i])
ans[v.id]=(ans[v.id]+1ll*v.opt*query(1,1,n,v.l,v.r,i))%mod;
}
for(int i=1;i<=q;i++) printf("%d\n",ans[i]);
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 6216kb
input:
3 1 1 8 1 6 2 3 2 2 2 0 0
output:
[2 2 10] [3 3 100] [1 1 64] {174} 1
result:
wrong output format Expected integer, but "[2" found