LINK:地图
考虑如果是一棵树怎么做 权值可以离散 那么可以直接利用dsu on tree+树状数组解决。
当然 也可以使用莫队 不过前缀和比较难以维护 外面套个树状数组又带了个log 套分块然后就可以了。
最暴力的当然是线段树合并了。
此时考虑这是个仙人掌 仔细画图 发现一些比较好的性质 某个点x 除了自己某个儿子的low比自己的dfn小 剩下的都大。
剩下的显然都可以造成贡献 利用dfn和low可以轻松判断 然后上线段树合并即可。
省空间的话可以直接离线 当然也可以在线做。
不过这个做法不是常规的 仙人掌一般和圆方树联系在一起。
直接从仙人掌想到构造圆方树 然后 那么就转换成上面的问题了。
一个细节:非负整数 包括0 别犯sb错误。
//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<ctime>
#include<cmath>
#include<cstdlib>
#include<cctype>
#include<algorithm>
#include<queue>
#include<stack>
#include<deque>
#include<vector>
#include<bitset>
#include<list>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
#define RE register
#define ll long long
#define putl(x) printf("%lld\n",x)
#define gt(x) scanf("%d",&x)
#define put(x) printf("%d\n",x)
#define get(x) x=read()
#define rep(p,n,i) for(int i=p;i<=n;++i)
#define vep(p,n,i) for(int i=p;i<n;++i)
#define fep(n,p,i) for(int i=n;i>=p;--i)
#define pii pair<int,int>
#define mod 998244353
#define sum0(i) t[i].sum0
#define sum1(i) t[i].sum1
#define pb push_back
#define l(i) t[i].l
#define r(i) t[i].r
#define mk make_pair
#define S second
#define F first
using namespace std;
char *fs,*ft,buf[1<<15];
inline char getc()
{
return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;
}
inline int read()
{
RE int x=0,f=1;RE char ch=getc();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getc();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getc();}
return x*f;
}
const int MAXN=100010,maxn=150010;
int n,m,Q,top,cnt,len,maxx,id,ans0,ans1,ss;
int dfn[MAXN],low[MAXN],root[MAXN],s[MAXN],q[MAXN],ans[MAXN];
int lin[MAXN],ver[maxn<<1],nex[maxn<<1],a[MAXN];
vector<pii>g[MAXN];
struct wy
{
int l,r;
int sum1,sum0;
}t[MAXN*21];
inline void add(int x,int y)
{
ver[++len]=y;
nex[len]=lin[x];
lin[x]=len;
}
inline void modify(int &p,int l,int r,int x)
{
if(!p)p=++id;
if(l==r)return sum1(p)=1,void();
int mid=(l+r)>>1;
if(x<=mid)modify(l(p),l,mid,x);
else modify(r(p),mid+1,r,x);
sum1(p)=sum1(l(p))+sum1(r(p));
sum0(p)=sum0(l(p))+sum0(r(p));
}
inline int merge(int x,int y,int l,int r)
{
if(!x||!y)return x|y;
if(l==r)
{
if(sum0(x)&&sum0(y))return x;
if(sum0(x)&&sum1(y))return y;
if(sum1(x)&&sum0(y))return x;
sum0(x)=1;sum1(x)=0;
return x;
}
int mid=(l+r)>>1;
l(x)=merge(l(x),l(y),l,mid);
r(x)=merge(r(x),r(y),mid+1,r);
sum1(x)=sum1(l(x))+sum1(r(x));
sum0(x)=sum0(l(x))+sum0(r(x));
return x;
}
inline void ask(int p,int l,int r,int L,int R)
{
if(L<=l&&R>=r)
{
ans0+=sum0(p);
ans1+=sum1(p);
return;
}
int mid=(l+r)>>1;
if(L<=mid)ask(l(p),l,mid,L,R);
if(R>mid)ask(r(p),mid+1,r,L,R);
}
inline void dfs(int x)
{
s[++top]=x;dfn[x]=low[x]=++cnt;
modify(root[x],0,maxx,a[x]);
for(int i=lin[x];i;i=nex[i])
{
int tn=ver[i];
if(!dfn[tn])
{
dfs(tn);
low[x]=min(low[x],low[tn]);
if(low[tn]>=dfn[x])
{
int y=s[top];ss=0;
while(y!=x)
{
q[++ss]=y;
y=s[--top];
}
rep(1,ss,i)root[x]=merge(root[x],root[q[i]],0,maxx);
}
}
else low[x]=min(low[x],dfn[tn]);
}
vep(0,g[x].size(),i)
{
ans0=ans1=0;
ask(root[x],0,maxx,0,min(maxx,ans[g[x][i].S]));
if(g[x][i].F==0)ans[g[x][i].S]=ans0;
else ans[g[x][i].S]=ans1;
}
}
int main()
{
//freopen("1.in","r",stdin);
get(n);get(m);
rep(1,n,i)get(a[i]),maxx=max(maxx,a[i]);
rep(1,m,i)
{
int get(x),get(y);
add(x,y);add(y,x);
}
get(Q);
rep(1,Q,i)
{
int get(op);
int get(x),get(y);
g[x].pb(mk(op,i));
ans[i]=y;
}
dfs(1);
rep(1,Q,i)put(ans[i]);
return 0;
}