QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#767291 | #7626. Quake and Rebuild | ship2077 | Judgement Failed | / | / | C++23 | 2.2kb | 2024-11-20 20:27:02 | 2024-11-20 20:27:02 |
Judging History
你现在查看的是最新测评结果
- [2024-11-20 20:27:49]
- hack成功,自动添加数据
- (/hack/1219)
- [2024-11-20 20:27:02]
- 评测
- 测评结果:Judgement Failed
- 用时:0ms
- 内存:0kb
- [2024-11-20 20:27:02]
- 提交
answer
#include<bits/stdc++.h>
using namespace std;
constexpr int M=2e5+5,B=400;
bool flag[M],vis[M],cur[M];
int n,m,x,y,op,mn,ans,tp,bel[M];
int L[M],R[M],fa[M],jump[M],dep[M],lazy[M];vector<int>node[M];
int read(){
int x=0;char ch=getchar();
while (!isdigit(ch)) ch=getchar();
while (isdigit(ch)) x=x*10+ch-48,ch=getchar();
return x;
}
void rebuild(int x){ flag[x]=1;
for (int i=L[x];i<=R[x];i++) fa[i]=max(fa[i]-lazy[x],1);
for (int i=L[x];i<=R[x];i++)
if (fa[i]<L[x]) jump[i]=fa[i],dep[i]=1;
else jump[i]=jump[fa[i]],dep[i]=dep[fa[i]]+1,flag[x]=0;
lazy[x]=0;
}
void upd1(int l,int r,int c){
for (int i=l;i<=r;i++) fa[i]=max(fa[i]-c,1);
rebuild(bel[l]);
}
void upd2(int l,int r,int c){
for (int i=l+1;i<r;i++){lazy[i]+=c;
if (lazy[i]>R[i]) lazy[i]=R[i];
if (!flag[i]) rebuild(i);
}
}
void update(int l,int r,int c){
if (bel[l]==bel[r]) return upd1(l,r,c),void();
upd1(l,R[bel[l]],c);upd2(bel[l],bel[r],c);upd1(L[bel[r]],r,c);
}
int Jump(int x){return max(1,jump[x]-lazy[bel[x]]);}
int Fa(int x){return max(1,fa[x]-lazy[bel[x]]);}
void insert(int x){
if (vis[x]) return ;
node[bel[x]].push_back(x);
vis[x]=1;mn=min(mn,x);
}
void build(int k){ ans=1;mn=n;
while (k--) insert(read());
for (int i=bel[n];i;i--)
if (!node[i].empty()){ bool fl=0;
for (auto x:node[i]){
const int tmp=Jump(x);
fl|=vis[tmp]||cur[tmp];cur[tmp]=1;
}
for (auto x:node[i]) cur[x]=0;
if (!fl){
if (node[i].size()==1&&node[i][0]==mn) break;
for (auto x:node[i]){
const int tmp=Jump(x);
ans+=dep[x];insert(tmp);
}
continue;
}
for (int j=R[i];j>=L[i];j--)
if (vis[j]){
if (j==mn) break;
ans++;insert(Fa(j));
}
}
for (int i=0;i<=bel[n];i++){
for (auto x:node[i]) vis[x]=0;
node[i].clear();
}
printf("%d\n",ans);
}
int main(){
n=read();m=read();
for (int i=2;i<=n;i++) fa[i]=read();
for (int i=1;i<=n;i++) bel[i]=(i-1)/B+1;
for (int i=1;i<=bel[n];i++) L[i]=R[i-1]+1,R[i]=R[i-1]+B;
L[1]=2;R[bel[n]]=n;
for (int i=1;i<=bel[n];i++) rebuild(i);
while (m--){
op=read();x=read();
if (op==1) y=read(),update(x,y,read());
if (op==2) build(x);
}
return 0;
}
Details
Failed to show details