QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#385958 | #7448. rfplca | Kevin5307 | TL | 0ms | 0kb | C++23 | 2.3kb | 2024-04-11 10:35:48 | 2024-04-11 10:35:48 |
answer
//Author: Kevin
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define ll long long
#define ull unsigned ll
#define pb emplace_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
#define longer __int128_t
void die(string S){puts(S.c_str());exit(0);}
ll val[400400],tag[400400];
int n,q;
const int B=500;
void update(int l,int r,ll v)
{
int lb=l/B,rb=r/B;
if(lb==rb)
{
for(int i=l;i<=r;i++)
val[i]+=v;
return ;
}
for(int i=l;i/B==lb;i++)
val[i]+=v;
for(int i=r;i/B==rb;i--)
val[i]+=v;
for(int i=lb+1;i<rb;i++)
tag[i]+=v;
}
ll query(int p)
{
return max(1ll,val[p]+tag[p/B]);
}
int lst[400400];
int nxt[400400],prv[400400];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>q;
for(int i=2;i<=n;i++)
{
int f;
cin>>f;
update(i,i,f);
}
set<int> st;
for(int i=2;i<=n;i++)
{
int f=query(i);
if(f/B!=i/B)
lst[i]=f;
else
{
lst[i]=lst[f];
if(sz(st))
{
nxt[*st.rbegin()]=i;
prv[i]=*st.rbegin();
}
st.insert(i);
}
}
int lastans=0;
while(q--)
{
int t;
cin>>t;
if(t==1)
{
int l,r,x;
cin>>l>>r>>x;
l^=lastans;
r^=lastans;
x^=lastans;
update(l,r,-x);
auto it=st.lower_bound(l);
if(it==st.end()||*it>r) continue;
int cur=*it;
while(cur<=r)
{
int f=query(cur);
if(f/B!=cur/B)
{
lst[cur]=f;
st.erase(cur);
lst[nxt[cur]]=lst[cur];
nxt[lst[cur]]=nxt[cur];
}
else
lst[cur]=lst[f];
cur=nxt[cur];
}
}
else
{
int u,v;
cin>>u>>v;
u^=lastans;
v^=lastans;
while(u/B!=v/B)
{
if(u<v) swap(u,v);
u=lst[u];
}
while(lst[u]!=lst[v])
{
u=lst[u];
v=lst[v];
}
while(u!=v)
{
if(u<v) swap(u,v);
u=query(u);
}
cout<<(lastans=u)<<'\n';
}
}
return 0;
}
詳細信息
Test #1:
score: 0
Time Limit Exceeded
input:
400000 400000 1 2 1 4 1 1 5 4 6 5 9 1 1 13 3 8 12 16 3 11 8 8 2 18 21 15 7 23 11 6 4 26 17 5 12 6 5 28 32 26 21 5 19 1 25 25 11 26 47 11 31 25 18 7 25 36 40 23 54 31 14 62 61 33 57 40 11 16 24 51 69 25 55 51 55 65 34 19 18 21 20 62 64 83 22 48 67 47 21 27 30 63 10 14 70 63 18 17 74 98 40 89 10 7 30 ...