Description

Rin是個特別好動的少女。
一天Rin來到了一個遙遠的都市。這個都市有N個建筑，編號從1到N，其中市中心編號為1，這個都市有M條雙向通行的街道，每條街道連接著兩個不同的建筑，其中某些街道首尾相連連接成了一個環。Rin通過長時間的走訪，已經清楚了這個都市的兩個特點：
從市中心出發可以到達所有的建筑物。
任意一條街道最多存在與一個簡單環中。令Rin心花怒放的是，每個建筑物都會有拉面售賣。拉面有很多不同的種類，但對于Rin而言只有油膩程度的不同，因此我們把油膩程度相同的拉面看做同一種拉面。由于不同建筑物的拉面的油膩程度可能不同，我們用一個正整數來表示拉面的油膩程度。
要知道，拉面可是Rin的最愛，但是現在到了下班高峰期，都市的交通變得非常的堵塞。Rin只能通過沒有被堵死的街道通行，去品嘗所在建筑物的拉面。
現在Rin想知道，如果她正在編號為x的建筑物，那么在從市中心到x的所有簡單路徑經過的街道都被堵死的情況下，Rin可以品嘗到的拉面中（注意沒有出現的拉面是不能算在里面的）：
油膩程度<=y且品嘗次數為奇數次的拉面有多少種？
油膩程度<=y且品嘗次數為偶數次的拉面有多少種？

Input

第一行兩個正整數N,M，含義如題所示。
第二行一共N個正整數，第i個數Ai表示第i個建筑物出售的拉面的油膩程度。
接下來M行，每行兩個正整數x,y，表示在建筑物x,y之間有一條雙向通行的街道。數據保證1<=x,y<=N。
接下來一行一個正整數Q，表示詢問個數。
接下來Q行每行三個非負整數ty,x,y，x表示詢問的建筑物編號，y表示油膩程度的限制，ty=0時表示詢問偶數，ty=1表示詢問奇數。

Output

一共q行，對于每個詢問輸出一個答案。

Sample Input

5 6
2 1 6 7 7
1 2
1 3
2 4
4 5
4 5
1 3
3
0 3 2
0 3 1
0 1 7

Sample Output

0
0
1

Data Constraint

提示：請注意數據范圍中的<= ，特殊條件中提到的y均為詢問中的y

Hint

3號建筑物只能到達它自己，而 1號建筑物可以到達所有建筑物。

Solution

• 看到這種區間的詢問問題，就可以考慮莫隊算法。

• 但是首先要把詢問節點對應的子樹轉化成一個個連續的區間。

• 于是先做一遍正常 tarjan ，再 dfs 一遍，如果一個點 x 連出去是 y，又滿足：

  low[y]≥dfn[x]

• 則將 y 作為 x 的子樹，否則就將 y 作為 low[y] 的子樹即可。

• 這樣對 n 個點分塊，再對值域也分塊，直接莫隊即可。

• 時間復雜度 O(NN??√) 。

Code

#include<cstdio> #include<algorithm> #include<cmath> #include<cctype> using namespace std; const int N=1e5+5; struct data {int l,r,ty,y,n,id; }f[N]; int tot,sn,sv; int first[N],nex[N*3],en[N*3]; int a[N],b[N],ans[N],g[N/100+5][2],cnt[N*10]; int dfn[N],low[N],num[N],id[N],size[N]; bool bz[N]; inline int read() {int X=0,w=0; char ch=0;while(!isdigit(ch)) w|=ch=='-',ch=getchar();while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();return w?-X:X; } inline void write(int x) {if(x>9) write(x/10);putchar(x%10+'0'); } inline int max(int x,int y) {return x>y?x:y; } inline int min(int x,int y) {return x<y?x:y; } inline void insert(int x,int y) {nex[++tot]=first[x];first[x]=tot;en[tot]=y; } void tarjan(int x,int y) {num[dfn[x]=low[x]=++tot]=x;for(int i=first[x];i;i=nex[i])if(en[i]^y)if(!dfn[en[i]]){tarjan(en[i],x);low[x]=min(low[x],low[en[i]]);}else low[x]=min(low[x],dfn[en[i]]); } void dfs(int x) {id[x]=++tot,bz[x]=size[x]=1;for(int i=first[x];i;i=nex[i])if(!bz[en[i]] && low[en[i]]>=dfn[x]){dfs(en[i]);size[x]+=size[en[i]];}for(int i=first[x];i;i=nex[i])if(!bz[en[i]]){dfs(en[i]);size[num[low[en[i]]]]+=size[en[i]];} } inline bool cmp(data x,data y) {return x.n<y.n || x.n==y.n && x.r<y.r; } inline void update(int x,bool p) {int pos=(b[x]-1)/sv+1;if(p){if(cnt[b[x]]&1) g[pos][0]++,g[pos][1]--; elseif(cnt[b[x]]) g[pos][0]--,g[pos][1]++; else g[pos][1]++;cnt[b[x]]++;}else{if(cnt[b[x]]==1) g[pos][1]--; elseif(cnt[b[x]]&1) g[pos][1]--,g[pos][0]++; else g[pos][1]++,g[pos][0]--;cnt[b[x]]--;} } inline int calc(int x,int p) {int sum=0,pos=(x-1)/sv+1;for(int i=1;i<pos;i++) sum+=g[i][p];for(int i=(pos-1)*sv+1;i<=x;i++)if(cnt[i] && (cnt[i]&1)==p) sum++;return sum; } int main() {int n=read(),m=read();for(int i=1;i<=n;i++) sv=max(sv,a[i]=read());sn=sqrt(n),sv=sqrt(sv);for(int i=1;i<=m;i++){int x=read(),y=read();insert(x,y);insert(y,x);}tarjan(1,tot=0);tot=0,dfs(1);for(int i=1;i<=n;i++) b[id[i]]=a[i];int q=read();for(int i=1;i<=q;i++){f[i].ty=read();int x=read();f[i].l=id[x],f[i].r=id[x]+size[x]-1;f[i].y=read();f[i].id=i,f[i].n=(f[i].l-1)/sn+1;}sort(f+1,f+1+q,cmp);for(int i=1,l=1,r=0;i<=q;i++){while(l>f[i].l) update(--l,true);while(r<f[i].r) update(++r,true);while(l<f[i].l) update(l++,false);while(r>f[i].r) update(r--,false);ans[f[i].id]=calc(f[i].y,f[i].ty);}for(int i=1;i<=q;i++) write(ans[i]),putchar('\n');return 0; } 與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的JZOJ 5629. 【NOI2018模拟4.4】Map的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。