offline query

/******************************************************************************

BOJ 16978 offline query

*******************************************************************************/

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

using ll=long long;
using pi = pair<ll,ll>;
const ll N = 3e6+100;
ll n,m,k,tc=1,a,b,c,d,now;
ll tree[N],arr[N];
struct u{ll a,b;};
struct q{
    ll idx,a,b,c;
    bool operator <(struct q chs){
        return a < chs.a; 
    };
};
vector<struct u> up;
vector<struct q> qr;

struct cmp{
    bool operator () (pi a, pi b) {
    return a.first > b.first;
}
};
ll init(ll N,ll s ,ll e){
	if(s==e) {
	    tree[N] = arr[s];
	    return tree[N];
	}
	ll mid=(s+e)/2;
	return tree[N]=init(N*2,s,mid)+init(N*2+1,mid+1,e);
}
void update(ll N,ll s,ll e,ll idx,ll val){
	if(idx>e||idx<s) return;
	if(s==e){
		if(idx==s) tree[N] = val;
		return;
	}
	ll mid=(s+e)/2;
	update(N*2,s,mid,idx,val);
	update(N*2+1,mid+1,e,idx,val);
	tree[N]=tree[N*2]+tree[N*2+1];
}
ll query(ll N,ll s,ll e, ll l, ll r){
	if(l>e || r<s) return 0;
	if(l<=s&&e<=r) return tree[N];
	ll mid=(s+e)/2;
	return query(N*2,s,mid,l,r)+query(N*2+1,mid+1,e,l,r);
}
void solve(){
    priority_queue <pi, vector<pi>,cmp> pq; // 이거 안 쓰고 그냥 배열로 해도 됨
    up.push_back({0,0});
	cin>>n;
	for(int i=0;i<n;i++) cin>>arr[i];
	init(1,0,n-1);
	cin>>m;
    for(int i = 0; i < m; i++){
		cin>>a;
		if(a == 1) {
		    cin>>b>>c;
		    up.push_back({b,c});
		}
		if(a == 2) {
		    cin>>b>>c>>d;
		    qr.push_back({i,b,c,d});
		}
	}
	sort(qr.begin(),qr.end());
	/*for(auto[x,y,z,w] : qr){
	    cout<<x<<" "<<y<<" "<<z<<" "<<w<<'\n';
	}*/
	for(int i = 0; i < up.size(); i++){
	   if(i >= 1) update(1,0,n-1,up[i].a-1,up[i].b);
	   while(now < qr.size() && qr[now].a == i) {
	       pq.push({qr[now].idx,query(1,0,n-1,qr[now].b-1,qr[now].c-1)});
	       now++;
	   }
	}
	while(!pq.empty()){cout<<pq.top().second<<'\n';pq.pop();}
	
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	while(tc--) solve();
	return 0;
}

/******************************************************************************

 13306 Union-Find + Offline query

*******************************************************************************/

#include <iostream>
#include <vector>
using namespace std;

int p[200010];int par[200010]; int h[200010];
int N,Q,a,b,c;
struct query{int a,b,c;};
vector<struct query> v;
vector<string> res;

int Find(int u)
{
	if(p[u]==-1) return u;
	return p[u] = Find(p[u]);
}
void Union(int u,int v)
{
	u=Find(u); v=Find(v);
    if(h[u]<h[v]) swap(u,v);
    p[v]=u;
    if(h[u]==h[v]) h[u]++;
}
int main() {
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>Q;
	for(int i = 1; i <= N; i++) p[i] = -1;
	for(int i=2;i<=N;i++)
	{
		int parent; cin>>parent;
		par[i] = parent;
	}
	int sz =Q + N -1;
	while(sz--)
	{
		int a;cin>>a;
		if(a == 1) {
		    cin>>b>>c;
		    v.push_back({1,b,c});
		}
		else {
		    cin>>b;
		    v.push_back({0,b,0});
		}
	}

	for(int i = Q+N-2; i >= 0; i--){
	    int x = v[i].a, y = v[i].b, z = v[i].c;
	 //   cout<<x<<" "<<y<<" "<<z<<'\n';
	    if(x == 0) {
	      //  cout<<p[y]<<" ";
	        Union(y,par[y]);
	    }
	    else{
	        if(Find(y) == Find(z)) res.push_back("YES");
	        else res.push_back("NO");
	    } 
	}
	for(int i = res.size()-1; i>=0; i--) cout<<res[i]<<'\n';
	return 0;
}
/******************************************************************************

 17469 Union-Find + Offline query + Small to Large

*******************************************************************************/

#include <iostream>
#include <vector>
#include <algorithm>
#include <set> // 중복된 것도 없애주고, 오름차순 정렬도 해줌
using namespace std;

int p[100010];
int par[100010]; 
int N,Q,a,b,now;
struct query{int a,b;};
vector<struct query> v;
int res[1000010];
set<int> c [100010];

int Find(int u)
{
	if(p[u] == u) return u;
	return p[u] = Find(p[u]);
}
bool Union(int u,int v)
{
	u = Find(u); v = Find(v);
	if(u == v) return false;
	// small to large
    if(c[u].size() <= c[v].size()) swap(u,v);
    p[v]=u;
    for(auto i : c[v]) c[u].insert(i); // O(logN) x + x <= x + y
    c[v].clear();
    return true;
}
int main() {
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>Q;
	for(int i=2;i<=N;i++) cin>>par[i];
	for(int i = 1,x; i <= N; i++) {cin>>x;c[i].insert(x);p[i]= i;}
	int sz = N + Q - 1;
	while(sz--)
	{
		cin>>a>>b;
		if(a == 1) v.push_back({1,b});
		else v.push_back({2,b});
	}
    reverse(v.begin(),v.end());
	for(auto[x,y] : v){
	    if(x == 1) 
	        Union(y,par[y]);
	    else
	        res[now++] = c[Find(y)].size();
	    
	}

	for(int i = now-1; i >= 0; i--) cout<<res[i]<<'\n';
	
	return 0;
}