mo`s 추천문제에 있길래
https://www.acmicpc.net/problem/2912
이거랑 똑같이 풀리나해서 했는데
N하고 Q가 500000 이였다...
첨엔 그냥 백설공주와 난쟁이 저 문제랑 똑같이 제출했었다
sqrt decompositon+오프라인쿼리 로 접근했는데 찾아보니깐 이 풀이는
O((N+Q) x N^1/2 + Q x MAXN(종류의 최대치)) 이라서 터진다
시간초과 코드
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
int N,M;int sqrtN;int table[500001];
int MAXN = 0;
vector<int> v;vector<int> ret;
struct query
{
int idx,i,j;
};
bool cmp(query &a,query &b){
if(a.i/sqrtN!=b.i/sqrtN) return a.i<b.i;
return a.j<b.j;
}
vector<query> q;
void find(int idx,int k){
for(int i=1;i<=MAXN;i++){
if(table[i]>k){
ret[idx]=i;
return ;
}
}
ret[idx]=0;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>N>>M;sqrtN=(int)sqrt(N);
for(int i=0;i<N;i++){
int a;cin>>a;
v.push_back(a);
MAXN = max(MAXN,a);
}
for(int i=0;i<M;i++){
int a,b;cin>>a>>b;
q.push_back({i,a-1,b-1});
}
sort(q.begin(),q.end(),cmp);
int s = q[0].i; int e = q[0].j;
int ans = 0;
ret.resize(q.size());
int ite = (e-s+1)/2;
for(int i=s;i<=e;i++){
table[v[i]]++;
}
find(q[0].idx,ite);
for(int x=1;x<M;x++){
while(s<q[x].i){
table[v[s++]]--;
}
while(s>q[x].i){
table[v[--s]]++;
}
while(e<q[x].j){
table[v[++e]]++;
}
while(e>q[x].j){
table[v[e--]]--;
}
ite = (e-s+1)/2;
find(q[x].idx,ite);
}
for(int i=0;i<M;i++){
cout<<ret[i]<<"\n";
}
}
AC 받은 풀이
세그트리
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
int N,M;int MAXN = 0;
vector<int> v; vector<int> idx[500001];
int segtree[500001*4];
void init(int s,int e,int node){
if(s==e){
segtree[node]=v[s]; return;
}
int mid = (s+e)/2;
init(s,mid,node*2);
init(mid+1,e,node*2+1);
int ll = segtree[node*2];
int cnt = upper_bound(idx[ll].begin(),idx[ll].end(),e)-
lower_bound(idx[ll].begin(),idx[ll].end(),s)+1;
if(cnt>(e-s+1)/2){
segtree[node]=ll;return;
}
int rr = segtree[node*2+1];
cnt = upper_bound(idx[rr].begin(),idx[rr].end(),e)-
lower_bound(idx[rr].begin(),idx[rr].end(),s)+1;
if(cnt>(e-s+1)/2){
segtree[node]=rr;return ;
}
segtree[node]=0;
}
int query(int s,int e,int node,int l,int r){
if(s>r||e<l) return 0;
if(l<=s&&e<=r){
int cnt = upper_bound(idx[segtree[node]].begin(),idx[segtree[node]].end(),r)-
lower_bound(idx[segtree[node]].begin(),idx[segtree[node]].end(),l);
if(cnt>(r-l+1)/2){
return segtree[node];
}
return 0;
}
int mid = (s+e)/2;
int left = query(s,mid,node*2,l,r);
int right = query(mid+1,e,node*2+1,l,r);
if(left>0) return left;
if(right>0) return right;
return 0;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>N>>M;
for(int i=0;i<N;i++){
int a;cin>>a;
v.push_back(a);
idx[a].push_back(i);
MAXN = max(MAXN,a);
}
for(int i=1;i<=MAXN;i++){
sort(idx[i].begin(),idx[i].end());
}
init(0,N-1,1);
for(int i=0;i<M;i++){
int a,b;cin>>a>>b;
cout<<query(0,N-1,1,a-1,b-1)<<"\n";
}
}
idx 배열, 이걸로 이분탐색하면서 트리값 채워주면 된다.