QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#825261 | #9774. Same Sum | ucup-team073# | TL | 207ms | 117728kb | C++23 | 5.2kb | 2024-12-21 17:54:48 | 2024-12-23 17:07:38 |
Judging History
你现在查看的是最新测评结果
- [2025-01-11 11:59:18]
- hack成功,自动添加数据
- (/hack/1443)
- [2024-12-23 17:02:06]
- hack成功,自动添加数据
- (/hack/1310)
- [2024-12-23 16:48:26]
- hack成功,自动添加数据
- (/hack/1309)
- [2024-12-23 16:33:45]
- hack成功,自动添加数据
- (/hack/1308)
- [2024-12-23 16:23:53]
- hack成功,自动添加数据
- (/hack/1307)
- [2024-12-23 16:13:08]
- hack成功,自动添加数据
- (/hack/1306)
- [2024-12-23 15:54:42]
- hack成功,自动添加数据
- (/hack/1305)
- [2024-12-23 14:58:39]
- hack成功,自动添加数据
- (/hack/1304)
- [2024-12-23 09:58:11]
- hack成功,自动添加数据
- (/hack/1302)
- [2024-12-23 09:47:22]
- hack成功,自动添加数据
- (/hack/1301)
- [2024-12-23 09:41:23]
- hack成功,自动添加数据
- (/hack/1300)
- [2024-12-23 09:26:32]
- hack成功,自动添加数据
- (/hack/1299)
- [2024-12-23 09:19:58]
- hack成功,自动添加数据
- (/hack/1298)
- [2024-12-23 09:13:29]
- hack成功,自动添加数据
- (/hack/1297)
- [2024-12-22 18:52:18]
- hack成功,自动添加数据
- (/hack/1296)
- [2024-12-22 18:13:14]
- hack成功,自动添加数据
- (/hack/1294)
- [2024-12-21 17:54:48]
- 提交
answer
#include <bits/stdc++.h>
#define int long long
#define lc p<<1
#define rc p<<1|1
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar())f^=ch=='-';
for(;isdigit(ch);ch=getchar())x=x*10+(ch^48);
return f?x:-x;
}
inline int qpow(int x,int t,int mo){
int ret=1;
for(;t;t>>=1,x=x*x%mo)if(t&1)ret=ret*x%mo;
return ret;
}
struct Hash{
int a[4];
Hash(int x,int y,int z,int w){
a[0]=x,a[1]=y,a[2]=z,a[3]=w;
}
Hash(){a[0]=a[1]=a[2]=a[3]=0;}
Hash operator + (Hash x){
Hash ret;
for(int i=0;i<4;++i)ret.a[i]=a[i]+x.a[i];
return ret;
}
Hash operator - (Hash x){
Hash ret;
for(int i=0;i<4;++i)ret.a[i]=a[i]-x.a[i];
return ret;
}
Hash operator * (Hash x){
Hash ret;
for(int i=0;i<4;++i)ret.a[i]=a[i]*x.a[i];
return ret;
}
Hash operator % (Hash x){
Hash ret;
for(int i=0;i<4;++i)ret.a[i]=a[i]%x.a[i];
return ret;
}
bool operator == (Hash x){
for(int i=0;i<4;++i)if(x.a[i]!=a[i])return 0;
return 1;
}
bool operator != (Hash x){
for(int i=0;i<4;++i)if(x.a[i]!=a[i])return 1;
return 0;
}
};
const Hash mo(998244353,993244853,1e9+7,1e9+9);
const Hash bas(1009,997,2909,3881);
const int N=2e5+5,inf=1e12;
Hash pw[N],ipw[N];
void red(Hash &x){
for(int i=0;i<4;++i)if(x.a[i]>=mo.a[i])
x.a[i]-=mo.a[i];
}
int n,a[N],q;
struct SegmentTree{
Hash val[N<<2],mdf[N<<2];
void pushdown(int p){
val[lc]=val[lc]*mdf[p]%mo;
val[rc]=val[rc]*mdf[p]%mo;
mdf[lc]=mdf[lc]*mdf[p]%mo;
mdf[rc]=mdf[rc]*mdf[p]%mo;
mdf[p]=Hash(1,1,1,1);
}
void pushup(int p){
red(val[p]=val[lc]+val[rc]);
}
void modify(int p,int l,int r,int L,int R,Hash d){
if(L<=l&&r<=R){
val[p]=val[p]*d%mo;
mdf[p]=mdf[p]*d%mo;
}else{
pushdown(p);
int mid=(l+r)>>1;
if(L<=mid)modify(lc,l,mid,L,R,d);
if(mid<R)modify(rc,mid+1,r,L,R,d);
pushup(p);
}
}
Hash query(int p,int l,int r,int L,int R){
if(L<=l&&r<=R)return val[p];
else{
pushdown(p);
int mid=(l+r)>>1;
Hash ret=Hash(0,0,0,0);
if(L<=mid)red(ret=ret+query(lc,l,mid,L,R));
if(mid<R)red(ret=ret+query(rc,mid+1,r,L,R));
return ret;
}
}
void build(int p,int l,int r,int tag){
mdf[p]=Hash(1,1,1,1);
if(l==r)val[p]=tag?pw[a[l]]:ipw[a[l]];
else{
int mid=(l+r)>>1;
build(lc,l,mid,tag);
build(rc,mid+1,r,tag);
pushup(p);
}
}
}T1,T2;
struct sgt{
int minf[N<<2],maxf[N<<2],add[N<<2];
void pushdown(int p){
minf[lc]+=add[p];
minf[rc]+=add[p];
maxf[lc]+=add[p];
maxf[rc]+=add[p];
add[lc]+=add[p];
add[rc]+=add[p];
add[p]=0;
}
void pushup(int p){
minf[p]=min(minf[lc],minf[rc]);
maxf[p]=max(maxf[lc],maxf[rc]);
}
void modify(int p,int l,int r,int L,int R,int d){
if(L<=l&&r<=R){
add[p]+=d;
minf[p]+=d;
maxf[p]+=d;
}else{
pushdown(p);
int mid=(l+r)>>1;
if(L<=mid)modify(lc,l,mid,L,R,d);
if(mid<R)modify(rc,mid+1,r,L,R,d);
pushup(p);
}
}
int query1(int p,int l,int r,int L,int R){
if(L<=l&&r<=R){
return minf[p];
}else{
pushdown(p);
int mid=(l+r)>>1,ret=inf;
if(L<=mid)ret=min(ret,query1(lc,l,mid,L,R));
if(mid<R)ret=min(ret,query1(rc,mid+1,r,L,R));
return ret;
}
}
int query2(int p,int l,int r,int L,int R){
if(L<=l&&r<=R)return maxf[p];
else{
pushdown(p);
int mid=(l+r)>>1,ret=0;
if(L<=mid)ret=max(ret,query2(lc,l,mid,L,R));
if(mid<R)ret=max(ret,query2(rc,mid+1,r,L,R));
return ret;
}
}
}arr;
Hash fpow(Hash x,int t){
Hash ret=Hash(1,1,1,1);
for(;t;t>>=1,x=x*x%mo)if(t&1)ret=ret*x%mo;
return ret;
}
signed main(){
pw[0]=ipw[0]=Hash(1,1,1,1);
for(int i=1;i<N;++i){
pw[i]=pw[i-1]*bas%mo;
for(int j=0;j<4;++j){
ipw[i].a[j]=qpow(pw[i].a[j],mo.a[j]-2,mo.a[j]);
}
}
n=read(),q=read();
for(int i=1;i<=n;++i){
a[i]=read();
arr.modify(1,1,n,i,i,a[i]);
}
T1.build(1,1,n,1),T2.build(1,1,n,0);
while(q--){
int opt=read(),l=read(),r=read();
if(opt==1){
int v=read();
arr.modify(1,1,n,l,r,v);
T1.modify(1,1,n,l,r,pw[v]);
T2.modify(1,1,n,l,r,ipw[v]);
}else{
int tmp=arr.query1(1,1,n,l,r)+arr.query2(1,1,n,l,r);
Hash F=T1.query(1,1,n,l,r);
Hash G=T2.query(1,1,n,l,r);
Hash fuck=fpow(bas,tmp);
G=G*fuck%mo;
if(F==G)puts("YES");
else puts("NO");
}
}
}
详细
Test #1:
score: 100
Accepted
time: 207ms
memory: 117728kb
input:
8 4 1 2 3 4 5 6 7 8 2 1 8 1 1 4 4 2 1 6 2 1 8
output:
YES NO YES
result:
ok 3 token(s): yes count is 2, no count is 1
Test #2:
score: -100
Time Limit Exceeded
input:
200000 200000 0 0 0 1 1 0 2 1 1 2 0 1 0 0 0 2 1 0 1 2 2 1 2 1 2 0 0 2 1 2 1 0 0 2 0 2 1 1 1 2 0 0 0 0 2 0 1 0 0 2 2 1 1 0 0 2 1 0 2 0 2 1 2 1 0 1 2 1 0 1 2 1 2 1 0 1 2 0 1 0 1 1 0 2 1 2 0 2 2 1 1 2 1 2 2 0 0 1 2 0 0 2 2 0 1 2 2 0 0 1 2 1 2 0 2 0 0 2 0 2 1 0 1 1 1 1 2 1 2 0 1 2 1 0 2 1 0 1 1 2 2 0 1 ...
output:
NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO ...