QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#721769 | #8338. Quad Kingdoms Chess | AnotherDayofSun# | RE | 0ms | 0kb | C++14 | 2.5kb | 2024-11-07 16:47:38 | 2024-11-07 16:47:39 |
answer
#include<bits/stdc++.h>
#define For(i,j,k) for(int i=(j);i<=(k);i++)
#define re
#define vi vector<int>
#define pb push_back
#define ll long long
#define P 998244353
using namespace std;
inline int read(){
re char c;int res=0;bool flag=0;
while(c=getchar(),c<48)(c=='-')&&(flag=1);
do res=(res<<3)+(res<<1)+(c^48);
while(c=getchar(),c>47);
flag&&(res=-res);
return res;
}
const int MN=1e5+5;
int n,a[MN];
struct ds {
static const int N=MN<<2;
#define ls (k<<1)
#define rs (k<<1|1)
#define mid ((l+r)>>1)
int mx[N],cnt[N];
ll sum[N],ans[N];
void qry2(int k,int l,int r,int &tcnt,ll &tsum,ll &tans,int nowmx) {
if(l==r) {
if(mx[k]>=nowmx) tcnt=cnt[k],tsum=sum[k],tans=ans[k];
else tcnt=0,tsum=0,tans=0;
return;
}
if(mx[rs]>=nowmx) {
qry2(rs,mid+1,r,tcnt,tsum,tans,nowmx);
int lcnt=cnt[k]-cnt[rs];
int lsum=sum[k]-sum[rs];
int lans=(ans[k]-ans[rs])-lsum*cnt[rs];
tcnt+=lcnt,tsum+=lsum,tans+=lans;
} else qry2(ls,l,mid,tcnt,tsum,tans,nowmx);
}
void pushup(int k,int l,int r) {
mx[k]=max(mx[ls],mx[rs]);
if(mx[rs]>mx[ls]) cnt[k]=cnt[rs],sum[k]=sum[rs],ans[k]=ans[rs];
else {
int tcnt; ll tsum,tans;
qry2(ls,l,mid,tcnt,tsum,tans,mx[rs]);
cnt[k]=tcnt+cnt[rs],sum[k]=tsum+sum[rs],ans[k]=tans+tsum*cnt[rs]+ans[rs];
}
}
void upd(int k,int l,int r,int p,int v) {
if(l==r) {
mx[k]=sum[k]=ans[k]=v;
cnt[k]=1;
return;
}
if(p<=mid) upd(ls,l,mid,p,v);
else upd(rs,mid+1,r,p,v);
pushup(k,l,r);
}
void build(int k,int l,int r,int *a) {
if(l==r) {
mx[k]=sum[k]=ans[k]=a[l];
cnt[k]=1;
return;
}
build(ls,l,mid,a),build(rs,mid+1,r,a);
pushup(k,l,r);
}
pair<ll,int> qry() {
return make_pair(ans[1],cnt[1]);
}
#undef mid
};
struct tpw {
static const int N=4e5+5;
int n,a[N]; ds t;
void rd() {
n=read();
For(i,1,n) a[i]=read();
t.build(1,1,n,a);
}
void mdf(int x,int y) {
a[x]=y;
t.upd(1,1,n,x,y);
}
pair<ll,int> qry() {
return t.qry();
}
} line[2];
void works() {
line[0].rd();
line[1].rd();
int m=read();
while(m--) {
int o=read(),x=read(),y=read();
line[o-1].mdf(x,y);
// cerr<<line[0].qry().first<<' '<<line[1].qry().first<<endl;
if(line[0].qry()==line[1].qry()) printf("YES\n");
else printf("NO\n");
}
}
signed main() {
freopen("e.in","r",stdin);
freopen("e.out","w",stdout);
int T=1;
while(T--) {
works();
}
return 0;
}
详细
Test #1:
score: 0
Dangerous Syscalls
input:
5 1 2 3 4 5 5 5 4 3 2 1 8 1 1 5 1 4 2 1 2 4 1 5 1 1 5 5 2 1 4 2 3 5 2 5 5