QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#383639 | #6533. Traveling in Cells | tjf4 | TL | 193ms | 18048kb | C++20 | 4.5kb | 2024-04-09 16:11:14 | 2024-04-09 16:11:15 |
Judging History
answer
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<pii> vii;
typedef vector<int> vi;
const int inf=0x3f;
const int N=1e5+10;
ll n,m;
ll p[N],q[N],c[N];
int lowbit(int x) {
return x&(-x);
}
void add(ll x,ll d) {
for(int i=x;i<=n;i+=lowbit(i)) c[i]+=d;
}
ll qry(ll x) {
ll res=0;
for(int i=x;i>=1;i-=lowbit(i)) res+=c[i];
return res;
}
ll ls[2][N],mp[N];
ll Tr[2][N<<2],up[2][N<<2];//两棵,区间赋值,区间求和
//懒标记初始化成不可能出现的值
void build(int rt,int l,int r,int op)
{
Tr[op][rt]=0;
up[op][rt]=-1;
if(l==r)
{
Tr[op][rt]=ls[op][l];
return ;
}
int mid=(l+r)>>1;
build(rt<<1,l,mid,op);
build(rt<<1|1,mid+1,r,op);
Tr[op][rt]=Tr[op][rt<<1]+Tr[op][rt<<1|1];
}
void push_down(int rt,int l,int r,int op)
{
if(up[op][rt]!=-1)
{
ll mid=(l+r)>>1;
Tr[op][rt<<1]=up[op][rt]*(mid-l+1);
Tr[op][rt<<1|1]=up[op][rt]*(r-mid);
up[op][rt<<1]=up[op][rt];
up[op][rt<<1|1]=up[op][rt];
up[op][rt]=-1;
}
}
void update(int rt,int l,int r,int x,int y,ll val,int op)//将 [x,y] 内的数赋值成 val
{
if(up[op][rt]!=-1) push_down(rt,l,r,op);
if(x<=l&&r<=y)
{
Tr[op][rt]=val*(r-l+1);
up[op][rt]=val;
return ;
}
int mid=(l+r)>>1;
if(x<=mid) update(rt<<1,l,mid,x,y,val,op);
if(y>mid) update(rt<<1|1,mid+1,r,x,y,val,op);
Tr[op][rt]=Tr[op][rt<<1]+Tr[op][rt<<1|1];
}
ll query(int rt,int l,int r,int x,int y,int op)//求[x,y]的和
{
if(x<1||x>n) return 0;
if(up[op][rt]!=-1) push_down(rt,l,r,op);
if(l==r) return Tr[op][rt];
ll mid=(l+r)>>1,sum=0;
if(x<=mid) sum+=query(rt<<1,l,mid,x,y,op);
if(y>mid) sum+=query(rt<<1|1,mid+1,r,x,y,op);
return sum;
}
void upd(int x,int y) {
p[x]=y;
if(n==1) return;
if(x==1) {
if(p[x]==p[x+1]) {
int y1=query(1,1,n,x+1,x+1,1);
if(x+1==n) y1=n+1;
update(1,1,n,x,x,y1,1);
update(1,1,n,x+1,y1-1,0,0);
}
else {
int y1=query(1,1,n,x+1,x+1,1);
if(x+1==n) y1=n+1;
update(1,1,n,x,x,x+1,1);
update(1,1,n,x+1,y1-1,x,0);
}
}
else if(x==n) {
if(p[x]==p[x-1]) {
int x1=query(1,1,n,x-1,x-1,0);
if(x-1==1) x1=0;
update(1,1,n,x,x,x1,0);
update(1,1,n,x1+1,x-1,n+1,1);
}
else {
int x1=query(1,1,n,x-1,x-1,0);
if(x-1==1) x1=0;
update(1,1,n,x,x,x-1,0);
update(1,1,n,x1+1,x-1,x,1);
}
}
else if(p[x]!=p[x-1]&&p[x]!=p[x+1]) {
int y1=query(1,1,n,x+1,x+1,1);
int x1=query(1,1,n,x-1,x-1,0);
update(1,1,n,x1+1,x-1,x,1);
update(1,1,n,x+1,y1-1,x,0);
update(1,1,n,x,x,x-1,0);
update(1,1,n,x,x,x+1,1);
}
else if(p[x]==p[x-1]&&p[x]==p[x+1]) {
int y1=query(1,1,n,x+1,x+1,1);
int x1=query(1,1,n,x-1,x-1,0);
update(1,1,n,x1+1,x-1,y1,1);
update(1,1,n,x+1,y1-1,x1,0);
update(1,1,n,x,x,x1,0);
update(1,1,n,x,x,y1,1);
}
else if(p[x]==p[x-1]) {
int y1=query(1,1,n,x+1,x+1,1);
int x1=query(1,1,n,x-1,x-1,0);
update(1,1,n,x1+1,x-1,x+1,1);
update(1,1,n,x+1,y1-1,x,0);
update(1,1,n,x,x,x1,0);
update(1,1,n,x,x,x+1,1);
}
else if(p[x]==p[x+1]) {
int y1=query(1,1,n,x+1,x+1,1);
int x1=query(1,1,n,x-1,x-1,0);
update(1,1,n,x1+1,x-1,x,1);
update(1,1,n,x+1,y1-1,x-1,0);
update(1,1,n,x,x,x-1,0);
update(1,1,n,x,x,y1,1);
}
}
void init() {
for(int i=0;i<=n+1;i++) {
c[i]=p[i]=q[i]=0;
ls[0][i]=ls[1][i]=0;
}
}
int g[1000010];
int main() {
IOS
int t;
cin>>t;
while(t--) {
cin>>n>>m;
init();
for(int i=1;i<=n;i++) cin>>p[i];
for(int i=1;i<=n;i++) {
cin>>q[i]; add(i,q[i]);
}
for(int i=1;i<=n;i++) {
if(i==1||p[i]!=p[i-1]) ls[0][i]=i-1;
else ls[0][i]=ls[0][i-1];
}
for(int i=n;i>=1;i--) {
if(i==n||p[i]!=p[i+1]) ls[1][i]=i+1;
else ls[1][i]=ls[1][i+1];
}
build(1,1,n,0);
build(1,1,n,1);
while(m--) {
int op; cin>>op;
if(op==2) {
ll x,y; cin>>x>>y;
add(x,-q[x]);
add(x,(q[x]=y));
}
else if(op==1) {
ll x,y; cin>>x>>y;
upd(x,y);
}
else if(op==3) {
int now,k; cin>>now>>k;
for(int i=1;i<=k;i++) {
cin>>g[i],mp[g[i]]=1;
}
int l=now,r=now;
while(l&&mp[p[l]]) l=query(1,1,n,l,l,0);
while(r<=n&&mp[p[r]]) r=query(1,1,n,r,r,1);
l++,r--;
cout<<qry(r)-qry(l-1)<<'\n';
for(int i=1;i<=k;i++) mp[g[i]]=0;
}
}
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 16008kb
input:
2 5 10 1 2 3 1 2 1 10 100 1000 10000 3 3 1 3 3 3 2 2 3 2 5 20000 2 3 200 3 3 2 1 3 3 3 3 1 2 3 1 3 4 2 1 100000 1 2 2 3 1 2 1 2 4 1 1 2 3 4 1000000 1000000 1000000 1000000 3 4 4 1 2 3 4
output:
100 110 1200 21211 100010 4000000
result:
ok 6 numbers
Test #2:
score: 0
Accepted
time: 129ms
memory: 15980kb
input:
20000 15 15 1 1 3 3 2 3 3 3 3 3 2 3 2 3 3 634593973 158136379 707704004 998369647 831633445 263092797 937841412 451774682 552617416 483763379 50360475 794662797 74247465 537217773 901809831 3 6 4 1 3 5 10 3 5 7 1 2 3 4 5 9 10 3 4 3 3 8 9 2 13 608033129 3 15 2 3 5 1 9 3 3 8 4 1 3 7 10 2 6 727472865 3...
output:
2689089686 8377825475 1706073651 1439027604 2689089686 792730352 8904867081 8904867081 8270273108 831633445 692051585 2782432626 697783016 883944422 184057757 287523250 184057757 696388752 184057757 1675459344 2667693025 2614711258 4006992373 1767091974 5348541057 5348541057 390631780 2290216252 942...
result:
ok 200062 numbers
Test #3:
score: 0
Accepted
time: 193ms
memory: 18048kb
input:
2000 150 150 8 3 8 8 8 6 8 4 2 7 6 8 8 5 8 7 7 8 5 6 8 8 6 8 8 8 8 7 8 6 6 8 8 8 6 2 3 4 8 8 7 8 5 8 2 6 8 7 8 8 6 8 6 8 3 8 8 8 8 4 7 8 7 3 7 6 7 5 5 8 6 8 8 6 3 8 6 7 6 8 8 7 4 8 6 7 8 7 7 7 7 8 8 8 8 2 5 2 8 8 6 7 6 3 8 8 7 8 8 8 6 6 8 6 6 7 5 8 8 8 7 8 7 7 6 8 8 8 8 8 8 6 5 7 5 5 8 7 8 7 7 7 6 5...
output:
4449391171 3290849667 852793841 5178673994 995994209 11431868919 4327723427 5071541023 3032743466 962345334 2997656427 4534278452 3851900075 3611231417 5071541023 1477584218 1299005818 1299005818 2145605244 854143763 886347565 2081234124 2333808475 2455955801 4179722063 2328504333 1473735464 4107685...
result:
ok 199987 numbers
Test #4:
score: -100
Time Limit Exceeded
input:
10 30000 30000 3 4 2 4 4 4 4 3 4 3 4 3 4 3 4 4 2 4 4 4 4 4 3 3 3 4 3 4 3 4 3 3 4 2 4 3 3 3 3 4 3 4 4 4 4 2 3 3 4 2 3 4 4 4 4 1 4 4 4 4 4 4 4 4 3 3 3 4 4 4 4 4 2 3 4 4 4 4 3 4 4 3 3 3 4 4 3 4 4 2 3 4 4 4 4 3 2 4 3 4 3 2 4 4 3 4 2 2 4 4 4 4 2 4 3 2 4 4 3 4 4 4 2 4 4 3 2 3 2 3 3 3 4 2 4 3 4 1 4 3 4 4 4...
output:
6959437173 934970676 72461245502 8365928740 8384151048 984567228 12482909122 1904927816 15134139942 3759040688 92670874909 332468911 5936663371 3562978848 1300592004 10314009201 5581540905 131246926443 15087184135864 4077066271 1124704817 1520626740 4388174158 744377942 2770411457 6231852240 1508724...