백준 17410 수열과 쿼리 1.5

문제 URL : https://www.acmicpc.net/problem/17410

 

문제 접근법: 

이전글 수열과 쿼리 18 문제와 동일합니다.

https://congsoony.tistory.com/423

백준 14504 수열과 쿼리 18

 

 

그치만 그대로 코드를 조금 바꿔서내면 런타임에러가

나올겁니다.

대체 무슨 이유인지 계속 찾아봤는데

제곱근분할이란게 반드시 제곱근형태로 분할할 필요는 없더군요

적당한 사이즈를 설정해서 분할해주도 상관이없습니다.

 

 

소스코드:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
//제곱근 분할법 sqrt Decomposition
int n,m;
vector<ll> arr;
vector<ll>bucket[100];
vector<tuple<ll,ll,ll,ll>> iv;
int sqrtN;
void input() {
	cin >> n;
   arr = vector<ll>(n*2);
   for(int i = 0;i<n;i++)cin>>arr[i];
}

void init(){
   sqrtN = 1200;
   for(int i =0;i<n;i++)bucket[i/sqrtN].push_back(arr[i]);
   for(int i =0;i<100;i++)sort(bucket[i].begin(),bucket[i].end());
}
void update(int x,ll val){
   int idx = x/sqrtN;
   bucket[idx].erase(lower_bound(bucket[idx].begin(),bucket[idx].end(),arr[x]));
   arr[x]=val;
   bucket[idx].insert(lower_bound(bucket[idx].begin(),bucket[idx].end(),val),val);
}
ll query(int l,int r,ll val){
   ll res = 0;
   while(l%sqrtN!=0 && l<=r)res+=arr[l++]>val;
   while((r+1)%sqrtN!=0&&l<=r)res+=arr[r--]>val;
   while(l<=r){
      int idx = l/sqrtN;
      res+= bucket[idx].end()-upper_bound(bucket[idx].begin(),bucket[idx].end(),val);
      l+=sqrtN;
   }
   return res;
}

void solve() {
   init();
   cin>>m;
   ll a,b,c,d;
   for(int i =0;i<m;i++){
      cin>>a>>b>>c;
      if(a==2){
         cin>>d;
         cout<<query(b-1,c-1,d)<<"\n";
      }
      else{
         update(b-1,c);
      }
   }
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	//freopen("input.txt", "r", stdin);
	input();
   solve();

}

 

 

 

 

 

여러번 시도했습니다.

정렬된상태를 유지할려고 multimap을 이용한방법도 써봤는데 시간초과나오고

 

분할사이즈를 몇으로정하는게 best인지는알수없으나 1200이 그나마 제일빠르더군요

 

 

 

 

궁금한점 혹은 모르는점 논리적인 오류등

어떤질문이든 댓글은 언제나 환영입니다.