BOJ 26087 - 피보나치와 마지막 수열과 쿼리

BOJ 26087 - 피보나치와 마지막 수열과 쿼리

결국 어떤 구간은 뒤에 오는 쿼리에 의해 덮어씌워지므로 쿼리를 뒤부터보며 특정 인덱스가 가장 먼저 포함되는 구간 쿼리에서 그 값을 갱신해주고 경로압축을 해준다.

DSU로 풀 수 있고 세그먼트 트리로도 풀 수 있다.

struct DSU {  
   vector<int> p;  
   DSU(int n) : p(n, -1) {}  
   int gp(int n) {  
      if (p[n] < 0) return n;  
      return p[n] = gp(p[n]);  
   }  
   void merge(int a, int b, int to_b = 1) {  
      a = gp(a), b = gp(b);  
      if (a == b) return;  
      if (!to_b && size(a) > size(b)) swap(a, b);  
      p[b] += p[a];  
      p[a] = b;  
   }  
   bool is_merged(int a, int b) { return gp(a) == gp(b); }  
   int size(int n) { return -p[gp(n)]; }  
};  
const ll mod = 1e9 + 7;  
inline ll md(ll x) { return md(mod, x); }  
  
int f[1000001];  
  
void solve() {  
   f[0] = 1, f[1] = 1;  
   for (int i = 2; i <= 1000000; i++) f[i] = md(f[i - 1] + f[i - 2]);  
   int n, q;  
   cin >> n >> q;  
   vi ret(n);  
   DSU dsu(n + 1);  
   vector<pi> qry(q);  
   for (auto &[l, r]: qry) cin >> l >> r, l--, r--;  
   for (int i = q - 1; i >= 0; i--) {  
      for (int j = qry[i].fi; j <= qry[i].se;) {  
         while (j <= qry[i].se && ret[j]) j = dsu.gp(j);  
         if (j <= qry[i].se) {  
            ret[j] = f[j - qry[i].fi + 1];  
            dsu.merge(j, j + 1);  
            j++;  
         }  
      }  
   }  
   for (int i = 0; i < n; i++) cout << ret[i] << ' ';  
}