强制在线。

在kruskal重构树上线段树合并即可。

题意有毒，ans = -1的时候下一次不异或。

1 /**************************************************************  2     Problem: 3551  3     Language: C++  4     Result: Accepted  5     Time:19204 ms  6     Memory:126608 kb  7 ****************************************************************/  8    9 #include 
      
        10 #include 
       
         11 #include 
        
          12   13 const int N = 100010, M = 500010, V = 8500010; 14   15 struct Edge { 16     int x, y, h; 17     inline bool operator <(const Edge &w) const { 18         return h < w.h; 19     } 20 }edge[M]; 21   22 int val[N], X[N]; 23 int ls[V], rs[V], sum[V], tot; 24 int num, fa[N * 2][20], h[N * 2], rt[N * 2], siz[N * 2], pw[N * 2]; 25   26 namespace ufs { 27     int fa[N * 2]; 28     inline void init(int n) { 29         for(int i = 1; i <= n; i++) { 30             fa[i] = i; 31         } 32         return; 33     } 34     int find(int x) { 35         if(x == fa[x]) return x; 36         return fa[x] = find(fa[x]); 37     } 38     inline void merge(int x, int y) { 39         fa[find(y)] = find(x); 40         return; 41     } 42     inline bool check(int x, int y) { 43         return find(x) == find(y); 44     } 45 } 46   47 int merge(int x, int y) { 48     if(!x || !y) return x | y; 49     int o = ++tot; 50     sum[o] = sum[x] + sum[y]; 51     ls[o] = merge(ls[x], ls[y]); 52     rs[o] = merge(rs[x], rs[y]); 53     return o; 54 } 55   56 void add(int p, int l, int r, int &o) { 57     if(!o) o = ++tot; 58     sum[o] = 1; 59     if(l == r) return; 60     int mid = (l + r) >> 1; 61     if(p <= mid) add(p, l, mid, ls[o]); 62     else add(p, mid + 1, r, rs[o]); 63     return; 64 } 65   66 int ask(int k, int l, int r, int o) { 67     //printf("%d %d %d %d \n", k, l, r, o); 68     if(l == r) return r; 69     int mid = (l + r) >> 1; 70     if(k <= sum[rs[o]]) return ask(k, mid + 1, r, rs[o]); 71     else return ask(k - sum[rs[o]], l, mid, ls[o]); 72 } 73   74 inline int getPos(int x, int H) { 75     int t = pw[num]; 76     while(t >= 0 && fa[x][0] && h[fa[x][0]] <= H) { 77         if(fa[x][t] && h[fa[x][t]] <= H) { 78             x = fa[x][t]; 79         } 80         t--; 81     } 82     return x; 83 } 84   85 int main() { 86   87     //freopen("in.in", "r", stdin); 88     //freopen("my.out", "w", stdout); 89   90     int n, m, q; 91     scanf("%d%d%d", &n, &m, &q); 92     num = n; 93     ufs::init(n + n); 94     for(int i = 1; i <= n; i++) { 95         scanf("%d", &val[i]); 96         X[i] = val[i]; 97     } 98     std::sort(X + 1, X + n + 1); 99     int xx = std::unique(X + 1, X + n + 1) - X - 1;100     for(int i = 1; i <= n; i++) {101         val[i] = std::lower_bound(X + 1, X + xx + 1, val[i]) - X;102         add(val[i], 1, xx, rt[i]);103         siz[i] = 1;104     }105     for(int i = 1; i <= m; i++) {106         scanf("%d%d%d", &edge[i].x, &edge[i].y, &edge[i].h);107     }108     std::sort(edge + 1, edge + m + 1);109     // build tree110     for(int i = 1; i <= m; i++) {111         int x = edge[i].x, y = edge[i].y;112         if(ufs::check(x, y)) {113             continue;114         }115         ++num;116         h[num] = edge[i].h;117         x = ufs::find(x);118         y = ufs::find(y);119         rt[num] = merge(rt[x], rt[y]);120         ufs::merge(num, x);121         ufs::merge(num, y);122         fa[x][0] = fa[y][0] = num;123         siz[num] = siz[x] + siz[y];124     }125     for(int i = 2; i <= num; i++) {126         pw[i] = pw[i >> 1] + 1;127     }128     for(int j = 1; j <= pw[num]; j++) {129         for(int i = 1; i <= num; i++) {130             fa[i][j] = fa[fa[i][j - 1]][j - 1];131         }132     }133  134     int lastans = 0;135     for(int i = 1, x, H, k; i <= q; i++) {136         scanf("%d%d%d", &x, &H, &k);137         if(lastans != -1) {x ^= lastans; H ^= lastans; k ^= lastans; }138         int y = getPos(x, H);139         if(siz[y] < k) puts("-1"), lastans = -1;140         else {141             lastans = X[ask(k, 1, xx, rt[y])];142             printf("%d\n", lastans);143         }144     }145  146     return 0;147 }