题解:
数据结构题,利用离线加树状数组统计答案
我们考虑这个问题的弱化版:给你N个数,求一个区间内不同的数字有多少个,这个问题可以通过记录每个权值上次出现的位置,在O(N
lgN)的时间内得到解决,具体的做法是将查询按右端点排序,从左向右枚举i,维护一个树状数组,其第k位表示k到i不同的数字有多少个,我们考虑将第i个数字加入,这时候,会树状数组中发生改变的仅仅是last[v]
+ 1到i这个区间内的值,其中v是第i位数字,last[v]表示v这个数上次出现的位置,如果没有出现过就为0。所以,我们把树状数组last[v]+1这个位置的值+1,把i+1这个位置-1,这样我们求和的时候,只要是左端点(对左端点求和)在last[v]+1之后(包括自身)的,就能将v这点给包括进来了。然后枚举到i之后,我们考虑右端点是i的全部查询,看其左端点在树状数组中的值是多少就可以了。
接下来我们来考虑我们这个问题,将树形结构转化成线性结构,那么我们就可以将问题转化为求一个区间内,恰好出现K次的权值有多少种。我们记录树状数组第k位表示k到i的答案,假设v出现的位置是在p1;
p2; p3; ; pk,那么我们假设现在枚举到了pk这个位置,将pk这个位置的数字加入集合之后,p(k−K−1)
+ 1到p(k−K)这部分区间内权值v出现次数就超过K了,p(k−K
)+ 1到p(k−K+1)这部分区间内权值v出现的次数恰好达到K,所以我们将树状数组中的p(k−K−1)
+ 1到p(k−K)内的值全部减1,p(k−K) +1到p(k−K+1)内的值全部加1。查询的时候是查询左端点前数的和。总体复杂度是O(N
lgN)的。
关键是想到变成线性序列,剩下也就简单了。
这是核心核心又核心的代码,应该好好体会的。
做题情况。刚刚表扬了自己,就又在数组大小上面栽了跟斗,这里建的是双向边,我却只开了满足单向的数组。不懂的是为什么杭电总是报的是WA呢?
还有就是初始化。L和c是必须重新初始化的。为什么? 因为上一case的L和c,会影响这个case。为什么?比如你上一次让L[i]有了一个值,然而这一次却还没访问到,那再dfs里面岂不是永远都访问不到?目测WA了有个把小时。
还有就是这题的作法十分令我佩服。但是我估计着这也是一个固定作法。如果以后再碰到此类型,应该就是水题一枚了。
还有两种作法。一种是线段树,一种是用map。
线段树的作法是插入删去一条线段。作法和之前的flowers很像,区间更新,单点查询。
树状数组核心代码:
for (int i=1; i<=n; i++){ int v = val[i]; pl[v].push_back(i); int g = pl[v].size()-1; if (g >= k){ if (g > k){ insert(pl[v][g-k-1]+1,-1); insert(pl[v][g-k]+1,1); } insert(pl[v][g-k]+1, 1); insert(pl[v][g-k+1]+1, -1); } while (qn[t].y==i){ ans[qn[t].id]=query(qn[t].x);//左端点向前的和 t++; } }
线段树核心代码:
for (int i = 1; i <= n; ++i) { // 线段树第j个数表示[j, i]间出现k次的数的个数 int num = a[i]; vv[num].push_back(i); int size = vv[num].size(); if (size >= k) { if (size > k) { // 1 ~ vv[num][size-k-1]都减1,就是删除这条线段 update(1, n, 1, 1, vv[num][size-k-1], -1); // vv[num][size-k-1]+1 ~ vv[num][size-k]都加1 ,插入 update(1, n, 1, vv[num][size-k-1] + 1, vv[num][size-k], 1); } else { // 加1 ,插入 update(1, n, 1, 1, vv[num][size-k], 1); } } while (Q[idx].r == i) { ans[Q[idx].id] = query(1, n, 1, Q[idx].l); idx++; } }
树状数组:
/* Pro: 0 Sol: date: */ #include <cstdio> #include <iostream> #include <cstring> #include <map> #include <iostream> #include <vector> #include <algorithm> #define maxn 100010 using namespace std; int n,k,t,a[maxn],Q,head[maxn],esub,linr[maxn],L[maxn],R[maxn],li,ans[maxn]; int c[maxn]; vector < int > pl[maxn];//用来记录值出现的位置 bool cmpx(int x, int y){ return a[x] < a[y]; } void dis(){ int tmp = -1,r[maxn]; for(int i = 1; i <= n; i ++) r[i] = i; sort(r + 1, r + 1 + n, cmpx); int prev = a[r[1]] - 1;//必须要有一个prev将原来的值记录下来,不然原来的值就保存不下来了 for(int i = 1; i <= n; i ++) if(prev != a[r[i]]) prev = a[r[i]],a[r[i]] = ++ tmp; else { a[r[i]] = tmp;} for(int i = 0; i <= tmp; i ++){ pl[i].clear();//初始化很重要 pl[i].push_back(0); //假设每个值都在第0个位置出现 } } struct query{ int L,R,id; bool operator < (const query& cmp) const{ return R < cmp.R; } }q[maxn]; struct Edge{ int v,nxt; }edge[maxn << 1 ];// void init(){ esub = 0; li = 0; memset(head,-1,sizeof(head)); memset(c,0,sizeof(c)); memset(L,0,sizeof(L)); } void add(int u, int v){ edge[esub].v = v; edge[esub].nxt = head[u]; head[u] = esub ++; } void dfs(int rt){ L[rt] = ++li; linr[li] = a[rt]; for(int j = head[rt]; j != -1; j = edge[j].nxt){ if(!L[edge[j].v]) dfs(edge[j].v); } R[rt] = li; } void modify(int pos, int val){ while(pos <= n){ c[pos] += val; pos += (pos & (-pos) ); } } int getsum(int pos){ int sum = 0; while(pos){ sum += c[pos]; pos -= (pos & (-pos) ); }return sum; } int main(){ scanf("%d",&t); for(int ca = 1; ca <= t; ca ++){ printf("Case #%d:\n",ca); scanf("%d%d",&n,&k); init();// for(int i = 1; i <= n; i ++){ scanf("%d",&a[i]); } dis();//从小到大离散化,可以不用从小到大,只要相同的依旧相同,不同的依旧不同就行 for(int i = 1; i < n; i ++){ int a,b; scanf("%d%d",&a,&b); add(a,b); add(b,a); } dfs(1); //产生一个线性序列 scanf("%d",&Q); for(int i = 1; i <= Q; i ++){ int x; scanf("%d",&x); q[i].L = L[x]; q[i].R = R[x]; q[i].id = i; } sort(q + 1, q + 1 + n); int qsub = 1; for(int i = 1; i <= n; i ++){ int v = linr[i]; pl[v].push_back(i);//记录linr[i]出现的位置 int g = pl[v].size() - 1; if(g >= k){ if(g > k){ modify(pl[v][g - k - 1] + 1, -1); modify(pl[v][g - k] + 1, 1); } modify(pl[v][g - k] + 1, 1); modify(pl[v][g - k + 1] + 1, -1); } while( q[qsub].R == i){ ans[q[qsub].id] = getsum(q[qsub].L); qsub ++; } } for(int i = 1; i <= Q; i ++) printf("%d\n",ans[i]); if(ca < t) puts(""); } return 0; }
线段树:(贴的)
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #include <vector> #include <map> using namespace std; const int maxn = 100010; int t, n, k, q; int w[maxn], a[maxn]; int L[maxn], R[maxn]; // 询问区间的左、右端点 int ans[maxn], id; vector<int> vt[maxn]; // 临接表 vector<int> vv[maxn]; bool vis[maxn]; map<int, int> mp; struct Query { int l, r, id; }Q[maxn]; // for segment tree: int add[maxn<<2]; bool cmp(Query q1, Query q2) { return q1.r < q2.r; } void dfs(int x) { // 将树形结构变成线性结构 vis[x] = true; L[x] = id; a[id] = w[x]; int size = vt[x].size(); for (int i = 0; i < size; ++i) { if (!vis[vt[x][i]]) { id++; dfs(vt[x][i]); } } R[x] = id; } void pushDown(int rt) { if (add[rt]) { add[rt<<1] += add[rt]; add[rt<<1|1] += add[rt]; add[rt] = 0; } return ; } void build(int l, int r, int rt) { add[rt] = 0; if (l == r) return ; int m = (l + r) >> 1; build(l, m, rt << 1); build(m + 1, r, rt << 1 | 1); } void update(int l, int r, int rt, int L, int R, int c) { if (L <= l && R >= r) { add[rt] += c; return ; } pushDown(rt); int m = (l + r) >> 1; if (L <= m) { update(l, m, rt << 1, L, R, c); } if (R > m) { update(m + 1, r, rt << 1 | 1, L, R, c); } } int query(int l, int r, int rt, int p) { if (l == r) { return add[rt]; } pushDown(rt); int m = (l + r) >> 1; if (p <= m) { return query(l, m, rt << 1, p); } else { return query(m + 1, r, rt << 1 | 1, p); } } int main() { scanf("%d", &t); for (int cas = 1; cas <= t; ++cas) { scanf("%d%d", &n, &k); mp.clear(); id = 1; for (int i = 1; i <= n; ++i) { scanf("%d", &w[i]); // 离散化 if (mp[w[i]] == 0) { mp[w[i]] = id++; } w[i] = mp[w[i]]; } int u, v; for (int i = 0; i < maxn; ++i) { vt[i].clear(); vv[i].clear(); } for (int i = 1; i < n; ++i) { scanf("%d%d", &u, &v); vt[u].push_back(v); vt[v].push_back(u); } memset(vis, false, sizeof(vis)); id = 1; dfs(1); scanf("%d", &q); for (int i = 0; i < q; ++i) { scanf("%d", &u); Q[i].id = i; Q[i].l = L[u]; Q[i].r = R[u]; } sort(Q, Q + q, cmp); build(1, n, 1); int idx = 0; for (int i = 1; i <= n; ++i) { // 线段树第j个数表示[j, i]间出现k次的数的个数 int num = a[i]; vv[num].push_back(i); int size = vv[num].size(); if (size >= k) { if (size > k) { // 1 ~ vv[num][size-k-1]都减1 update(1, n, 1, 1, vv[num][size-k-1], -1); // vv[num][size-k-1]+1 ~ vv[num][size-k]都加1 update(1, n, 1, vv[num][size-k-1] + 1, vv[num][size-k], 1); } else { // 加1 update(1, n, 1, 1, vv[num][size-k], 1); } } while (Q[idx].r == i) { ans[Q[idx].id] = query(1, n, 1, Q[idx].l); idx++; } } if (cas != 1) { printf("\n"); } printf("Case #%d:\n", cas); for (int i = 0; i < q; ++i) { printf("%d\n", ans[i]); } } return 0; }
用map写的(贴的):
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<map> #include<queue> #include<cmath> #define LL long long //c++提交的话 需要手动开栈(看解析上的) g++不用 但时间花费长 using namespace std; const int N=100005; int head[N];//邻接表 表头 struct node { int j; int next; } side[N*2]; int son[N];//儿子节点个数 int f[N];//保存父节点 int id[N];//某个节点对应相关数据存在了哪个map里面 //由于合并的关系 刚开始 i和id[i]对应相等 但一定的合并后就变了 int ans[N];//保存答案 离线保存要用 map<int ,int>str[N]; map<int ,int>:: iterator it,it1; queue<int>qu; int K; void build(int x,int i) { side[i].next=head[x]; head[x]=i; } void dfs(int x,int pre)//用dfs求的本节点的父节点 和儿子节点数 和将叶子节点加入队列 { int t=head[x]; f[x]=pre; while(t!=-1) { if(side[t].j!=pre) { dfs(side[t].j,x); ++son[x]; } t=side[t].next; } if(son[x]==0) { qu.push(x); } } void Add(int I,int i,int j)//将 map j 合并到i当中 将答案ans[I]进行更新 { for(it=str[j].begin(); it!=str[j].end(); ++it) //it 遍历map j 的元素 { it1=str[i].find(it->first);//到i 中查询 if(it1==str[i].end())//未找到 { str[i][it->first]=it->second;//加入 if(it->second==K)//如果正好等于K 则答案加一 ++(ans[I]); continue; } if(it1->second==K)//如果找到 本来在i中 这个数出现次数正好为K //在加上一个非0数则不等于K 了所以答案个数减1 --(ans[I]); if((it1->second+=it->second)==K)//如果加上正好为K 答案个数加1 这不会和上一个冲突 ++(ans[I]); } } int main() { int T; scanf("%d",&T); for(int cas=1; cas<=T; ++cas) { memset(head,-1,sizeof(head)); memset(ans,0,sizeof(ans)); memset(son,0,sizeof(son));//各种初始化 while(!qu.empty()) qu.pop(); int n,q; scanf("%d %d",&n,&K); for(int i=1; i<=n; ++i) { int a; str[i].clear();//清空 id[i]=i;//本来每个节点 的map 就是自己对应的 scanf("%d",&a); str[i][a]=1;//先都加入 本节点的数 if(K==1)//如果K正好为1 则答案也更新 ++ans[i]; } int x,y; for(int i=1; i<n; ++i) //输入边 建树 { scanf("%d %d",&x,&y); side[i].j=y; build(x,i); side[i+n].j=x; build(y,i+n); } dfs(1,0);//搜一个 while(!qu.empty()) { int l=qu.front();//取元素 qu.pop(); int fa=f[l];//fa为父亲节点 --son[fa];//父亲节点的可以更新的儿子节点减少1 if(son[fa]==0)//这是最后一个儿子节点 这是将fa加入队列 千万不能第一次更新就加入 { //否则会出现父节点在儿子节点前面的情况 就错了(自己输在这里了) 见上面数据 qu.push(fa); } int li=id[l];//找到对应的map int fai=id[fa]; if(str[fai].size()>str[li].size())//比较大小 {//小的往大的里面加 Add(fa,fai,li); } else{ ans[fa]=ans[l];//如果需要往l上合并 则先等于l的ans 在下面更新后ans[fa] //始终保存当前对应map里面的答案 id[fa]=li;//更改对应的map Add(fa,li,fai);//更新 } } scanf("%d",&q); printf("Case #%d:\n",cas); while(q--) { scanf("%d",&x); printf("%d\n",ans[x]); } if(cas<T) printf("\n"); } return 0; }