QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#385958#7448. rfplcaKevin5307TL 0ms0kbC++232.3kb2024-04-11 10:35:482024-04-11 10:35:48

Judging History

你现在查看的是最新测评结果

  • [2024-04-11 10:35:48]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [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 ...

output:


result: