BOJ 21607: Polynomial and Easy Queries

Link

• https://www.acmicpc.net/problem/21607
• 2021 SciCom Qualification Test 2E번

Tag

• Segment Tree
• Spare Table

Time Complexity

• $O(Q(lgN+lgQ)+XlgX)$ $(X=100003)$

$f(x)=2x^2-1,g(x)=4x^3-3x$이고, 길이 N의 수열 $A$가 주어진다. $f,g$를 구간에 적용하는 쿼리와 $A_i$를 $100003$으로 나눈 나머지를 구하는 쿼리가 주어진다. 이러한 쿼리를 $Q$개 처리해야 한다. 일단 $f,g$가 곱셈으로만 이루어져 있으니 나머지를 구하는건 그냥 해주면 될거 같고, $f,g$를 어떻게 하느냐가 문제다. 근데 왜 하필 $f,g$를 저렇게 줬을까? 뭔가 특별한 성질이 있나? 결론부터 말하자면 $f\cdot g=g\cdot f$다. 그래서 1,2번 쿼리가 어떤 순서로 들어왔는지는 중요하지 않고, 각각 $A_i$에 $f,g$가 각각 몇번 적용되었는지 알아내고 빠르게 계산할 수 있으면 된다.

 

$f,g$가 각각 몇번 적용되었는지는 range-update point-query 세그먼트 트리 두개면 된다. 실제 $A_i$를 빠르게 계산하는건 Sparse Table로 전처리하면 $O(lgQ)$에 가능하다.

 

Sparse Table 전처리에 $O(XlgX)$ $(X=100003)$, 1,2번 쿼리당 $O(lgN)$, 3번 쿼리당 $O(lgN+lgQ)$에 처리 가능하다. 대충 엔로그엔~~

Code

	#include <bits/stdc++.h>
	using namespace std;
	typedef long long ll;
	typedef pair<ll,ll> pll;
	typedef pair<int,int> pii;
	#define fi first
	#define se second
	#define endl '\n'
	#define y1 holyshit
	#define all(x) x.begin(),x.end()
	const int inf=0x3f3f3f3f;
	const int mod=100003;
	int N,Q,A[500010],f[100010][20],g[100010][20];
	int tree[2][1<<20];
	int base=1<<19;
	void update(int op,int l,int r){
	l+=base; r+=base;
	while(l<=r){
	if(l&1) tree[op][l]++;
	if(~r&1) tree[op][r]++;
	l=(l+1)>>1; r=(r-1)>>1;
	}
	}
	int query(int op,int p){
	int ret=0;
	for(p+=base;p;p>>=1) ret+=tree[op][p];
	return ret;
	}
	int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin>>N>>Q;
	for(int i=0;i<mod;i++){
	f[i][0]=(2LL*i*i-1+mod)%mod;
	g[i][0]=(4LL*i*i-3+mod)*i%mod;
	}
	for(int i=1;i<20;i++) for(int j=0;j<mod;j++){
	f[j][i]=f[f[j][i-1]][i-1];
	g[j][i]=g[g[j][i-1]][i-1];
	}
	for(int i=1;i<=N;i++) cin>>A[i];
	while(Q--){
	int t,l,r,x; cin>>t;
	if(t==3){
	cin>>x;
	int res=A[x], fcnt=query(0,x), gcnt=query(1,x);
	for(int i=0;i<20;i++) if((1<<i)&fcnt) res=f[res][i];
	for(int i=0;i<20;i++) if((1<<i)&gcnt) res=g[res][i];
	cout<<res<<endl;
	}
	else{
	cin>>l>>r;
	update(t-1,l,r);
	}
	}
	return 0;
	}

view raw 21607.cpp hosted with ❤ by GitHub