QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#540901 | #8133. When Anton Saw This Task He Reacted With 😩 | PhantomThreshold# | TL | 0ms | 3616kb | C++20 | 4.2kb | 2024-08-31 18:05:07 | 2024-08-31 18:05:10 |
Judging History
answer
#include<bits/stdc++.h>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>
#define ll long long
#define int long long
using namespace std;
const int MOD=998244353;
signed main()
{
ios_base::sync_with_stdio(false);
const int B=300,maxd=17;
struct vc
{
int x,y,z;
vc operator+(const vc &k)const{return (vc){(x+k.x)%MOD,(y+k.y)%MOD,(z+k.z)%MOD};}
vc operator-(const vc &k)const{return (vc){(x-k.x)%MOD,(y-k.y)%MOD,(z-k.z)%MOD};}
vc operator*(const int k)const{return (vc){(x*k)%MOD,(y*k)%MOD,(z*k)%MOD};}
vc operator*(const vc &k)const{return (vc){(y*k.z-z*k.y)%MOD,(z*k.x-x*k.z)%MOD,(x*k.y-y*k.x)%MOD};}
vc operator^(const vc &k)const{return (vc){(x*k.x)%MOD,(y*k.y)%MOD,(z*k.z)%MOD};}
};
int n,q;
cin>>n>>q;
vector<vc> a(n+5);
vector<int> L(n+5),R(n+5),pa(n+5);
vector<vector<int>> jmp(maxd+5,vector<int>(n+5));
for(int i=1;i<=n;i++)
{
string ty;
cin>>ty;
if(ty=="x")
{
cin>>L[i]>>R[i];
pa[L[i]]=i;pa[R[i]]=i;
}
else
{
cin>>a[i].x>>a[i].y>>a[i].z;
}
}
vector<pair<int,vc>> mods(q+5);
for(int i=1;i<=q;i++)
{
int pos;
vc d;
cin>>pos>>d.x>>d.y>>d.z;
mods[i]=make_pair(pos,d);
}
vector<int> dfn(n+5),dfne(n+5),dep(n+5);
int idx=0;
function<void(int)> dfs0=[&](int x)
{
dfn[x]=++idx;
if(L[x])
{
jmp[0][L[x]]=jmp[0][R[x]]=x;
dep[L[x]]=dep[R[x]]=dep[x]+1;
dfs0(L[x]);
dfs0(R[x]);
}
dfne[x]=idx;
};
dep[1]=1;
dfs0(1);
for(int d=1;d<=maxd;d++)
{
for(int i=1;i<=n;i++)
jmp[d][i]=jmp[d-1][jmp[d-1][i]];
}
auto lca=[&](int x,int y)
{
if(dep[x]>dep[y])swap(x,y);
for(int d=maxd;d>=0;d--)
{
if(dep[y]-(1<<d)>=dep[x])
y=jmp[d][y];
}
if(x==y)return x;
for(int d=maxd;d>=0;d--)
{
if(jmp[d][x]!=jmp[d][y])
x=jmp[d][x],y=jmp[d][y];
}
return jmp[0][x];
};
auto kthp=[&](int x,int k)
{
for(int d=maxd;d>=0;d--)
{
if((k>>d)&1)
x=jmp[d][x];
}
return x;
};
const vc X=(vc){1,0,0},Y=(vc){0,1,0},Z=(vc){0,0,1};
for(int l=1;l<=q;l+=B)
{
vector<int> gop(n+5),gopm(n+5),sp(n+5),csp(n+5);
vector<vc> cfx(n+5),cfy(n+5),cfz(n+5);
int r=min(q,l+B-1);
vector<int> tmp,tmp2;
tmp2.push_back(1);
for(int i=l;i<=r;i++)
{
tmp2.push_back(mods[i].first);
}
sort(tmp2.begin(),tmp2.end(),[&](int x,int y){return dfn[x]<dfn[y];});
tmp=tmp2;
for(int i=0;i+1<(int)tmp2.size();i++)
{
tmp.push_back(lca(tmp2[i],tmp2[i+1]));
}
sort(tmp.begin(),tmp.end(),[&](int x,int y){return dfn[x]<dfn[y];});
tmp.erase(unique(tmp.begin(),tmp.end()),tmp.end());
stack<int> s;
for(auto z:tmp)
{
sp[z]=1;
if(s.empty())s.push(z);
else
{
int pp=s.top();
while(not(dfn[pp]<=dfn[z] and dfne[z]<=dfne[pp]))
{
s.pop();
pp=s.top();
}
gop[z]=pp;
gopm[z]=kthp(z,dep[z]-dep[gop[z]]-1);
s.push(z);
}
}
function<void(int)> dfs1=[&](int u)
{
if(sp[pa[u]])
{
cfx[u]=X;
cfy[u]=Y;
cfz[u]=Z;
}
csp[u]=sp[u];
if(L[u])
{
dfs1(L[u]);
dfs1(R[u]);
if(csp[L[u]] or csp[R[u]])
csp[u]=1;
}
if(not sp[u])
{
if(csp[L[u]])
{
cfx[L[u]]=(X*a[R[u]])^cfx[u];
cfy[L[u]]=(Y*a[R[u]])^cfy[u];
cfz[L[u]]=(Z*a[R[u]])^cfz[u];
}
else
{
cfx[R[u]]=(a[L[u]]*X)^cfx[u];
cfy[R[u]]=(a[L[u]]*Y)^cfy[u];
cfz[R[u]]=(a[L[u]]*Z)^cfz[u];
}
}
if(L[u])a[u]=a[L[u]]*a[R[u]];
};
dfs1(1);
/*
cerr<<"---\n";
for(int j=1;j<=n;j++)
cerr<<a[j].x<<' '<<a[j].y<<' '<<a[j].z<<endl;
cerr<<"---\n";
for(auto z:tmp)cerr<<z<<' ';
cerr<<endl;
*/
reverse(tmp.begin(),tmp.end());
for(int i=l;i<=r;i++)
{
a[mods[i].first]=mods[i].second;
for(auto z:tmp)
{
if(L[z])
{
a[z]=a[L[z]]*a[R[z]];
}
vc tmp3;
tmp3=tmp3+cfx[z]*a[z].x;
tmp3=tmp3+cfy[z]*a[z].y;
tmp3=tmp3+cfz[z]*a[z].z;
if(gopm[z]!=z)a[gopm[z]]=tmp3;
}
cout<<a[1].x<<' '<<a[1].y<<' '<<a[1].z<<"\n";
/*
cerr<<"---\n";
for(int j=1;j<=n;j++)
cerr<<a[j].x<<' '<<a[j].y<<' '<<a[j].z<<endl;
cerr<<"---\n";
*/
}
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3616kb
input:
5 3 x 2 3 v 1 0 1 x 4 5 v 0 2 1 v 1 1 1 4 1 2 3 5 0 1 1 4 0 2 2
output:
-2 0 2 1 -2 -1 0 0 0
result:
ok 9 numbers
Test #2:
score: -100
Time Limit Exceeded
input:
199999 100000 x 137025 65661 v 572518668 158967010 74946561 x 129836 192657 x 141948 187810 v 574918069 328924434 141474729 x 143312 111002 x 52772 148497 v 922857701 690080961 651915759 v 656198340 28002884 129579416 v 639893144 265359784 646791226 v 796871409 411409966 598676495 v 882562617 224394...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...