hdu 4358 欧拉树形变线性+树状数组+离散化+离线+区间内出现k次的不同的数有几个+手动扩展栈

本文主要是介绍hdu 4358 欧拉树形变线性+树状数组+离散化+离线+区间内出现k次的不同的数有几个+手动扩展栈，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

http://acm.hdu.edu.cn/showproblem.php?pid=4358

性价比很高的一道题，一题练很多东西，逐一道来：
1、离散化的一种方法：

我在http://blog.csdn.net/u011026968/article/details/38542827里面写了一种离散化的方法，但是当时认为这种方法没法处理有重复元素的，这篇博客里的离散化的方法完善了我之前写的，可以保证相同元素离散化之后仍然相同，不同元素离散化之后仍然不同

其中a[]存的是待离散化的数

bool cmp(const int x,const int b)
{
return a[x]<a[b];
}
void dis()//离散化的方法---保证原来相等的还想等，不等的还不等，O(nlogn)
{
int tmpdis[MAXN];
for(int i=0;i<=N;i++)
tmpdis[i]=i;
sort(tmpdis+1,tmpdis+1+N,cmp);
int tmp=0,prev=a[tmpdis[1]]-1;//pre初始化的时候保证和第一个数不一样，因为已经排过序，所以最小的数-1满足需求
for(int i=1;i<=N;i++)
{
if(prev!=a[tmpdis[i]])
{
prev=a[tmpdis[i]];
a[tmpdis[i]]=++tmp;//两句不可以互换
}
else
{
a[tmpdis[i]]=tmp;
}
}
}

2、欧拉树形变线性

之前做过一道LCA的题---其实到现在还没有AC，，，学到的树形变线性，其实就是记录先序遍历的结果

调用直接dfs(root)，root为树根，最终在li[]里面存储了结果，以u为根的子树的区间是le[u],rig[u]，

void dfs(int u)
{vis[u]=1;le[u]=++treecnt;li[treecnt]=a[u];//已经离散化过的a[]for(int j=0;j<g[u].size();j++){int v=g[u][j];if(!vis[v])dfs(v);}rig[u]=treecnt;
}

3、树状数组+离线+区间内出现k次的不同的数有几个

我的方法参照之前一道CF的题：http://blog.csdn.net/u011026968/article/details/38589907

还看到一种方法：http://blog.csdn.net/julyana_lin/article/details/7872393

我看的不是很明白......不过跟我的另一篇博客应该是同样的方法：http://blog.csdn.net/u011026968/article/details/38583153

4、手动扩展栈

我RE了一下午，以为是自己的做法没想好导致错误-----然后手动模拟却觉得对，后来扩展栈，AC %>_<%

#pragma comment(linker, "/STACK:102400000,102400000")

其实G++交的话，不支持这句代码但是可以AC，不需要扩展栈

C++代码如下：

#pragma comment(linker, "/STACK:102400000,102400000")
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <iostream>
#include <iomanip>
#include <cmath>
#include <map>
#include <set>
#include <queue>
using namespace std;#define ls(rt) rt*2
#define rs(rt) rt*2+1
#define ll long long
#define ull unsigned long long
#define rep(i,s,e) for(int i=s;i<e;i++)
#define repe(i,s,e) for(int i=s;i<=e;i++)
#define CL(a,b) memset(a,b,sizeof(a))
#define IN(s) freopen(s,"r",stdin)
#define OUT(s) freopen(s,"w",stdout)const int MAXN = 100000+100;
int N,K;
int a[MAXN],vis[MAXN],tree[MAXN],treecnt;
int le[MAXN],rig[MAXN],c[MAXN*4],ans[MAXN];
int li[MAXN];vector<int>g[MAXN*2];struct Query
{int l,r,id;bool operator < (const Query &t)const{return r<t.r;}
}q[MAXN*4];inline int lowbit(int x){return x&(-x);}void add(int x, int v)
{while(x<=treecnt){c[x]+=v;x+=lowbit(x);}
}int sum(int x)
{int ret=0;while(x>0){ret+=c[x];x-=lowbit(x);}return ret;
}void dfs(int u)
{vis[u]=1;le[u]=++treecnt;li[treecnt]=a[u];//已经离散化过的a[]for(int j=0;j<g[u].size();j++){int v=g[u][j];if(!vis[v])dfs(v);}rig[u]=treecnt;
}void inittree()
{CL(tree,0);CL(vis,0);CL(le,0);CL(rig,0);treecnt=0;dfs(1);
}bool cmp(const int x,const int b)
{return a[x]<a[b];
}void dis()//离散化的方法---保证原来相等的还想等，不等的还不等，O(nlogn)
{int tmpdis[MAXN];for(int i=0;i<=N;i++)tmpdis[i]=i;sort(tmpdis+1,tmpdis+1+N,cmp);int tmp=0,prev=a[tmpdis[1]]-1;//pre初始化的时候保证和第一个数不一样，因为已经排过序，所以最小的数-1满足需求for(int i=1;i<=N;i++){if(prev!=a[tmpdis[i]]){prev=a[tmpdis[i]];a[tmpdis[i]]=++tmp;//两句不可以互换}else{a[tmpdis[i]]=tmp;}}
}
vector<int>data[MAXN];
int main()
{//IN("hdu4358.txt");int ncase,Q;int u,v,ic=0;scanf("%d",&ncase);while(ncase--){for(int i=0;i<MAXN;i++)data[i].clear();scanf("%d%d",&N,&K);for(int i=0;i<MAXN;i++)g[i].clear();///for(int i=1;i<=N;i++)scanf("%d",&a[i]);dis();//离散化for(int i=1;i<N;i++){scanf("%d%d",&u,&v);g[u].push_back(v);g[v].push_back(u);}inittree();//剩下的就是查找从scanf("%d",&Q);for(int i=1;i<=Q;i++){scanf("%d",&u);q[i].l=le[u];q[i].r=rig[u];q[i].id=i;//printf("u=%d l=%d r=%d\n",u,le[u],rig[u]);}sort(q+1,q+1+Q);/////for(int i=1;i<=treecnt;i++)// printf("a[%d]=%d li=%d\n",i,a[i],li[i]);///CL(c,0);for(int i=1,qu=1;i<=treecnt;i++)//{int vv=li[i];data[vv].push_back(i);int sz=data[vv].size();//K=li[i];if(sz>=K){add(data[vv][sz-K],1);if(sz>K)add(data[vv][sz-K-1],-2);if(sz>K+1)add(data[vv][sz-K-2],1);}while(q[qu].r==i && qu<=Q){ans[q[qu].id]=sum(i)-sum(q[qu].l-1);/////for(int i=1;i<=treecnt;i++)//   printf("##i=%d %d\n",i,c[i]);// printf("ans=%d id=%d l=%d r=%d\n",ans[q[qu].id],q[qu].id,q[qu].l,i);//qu++;}}printf("Case #%d:\n",++ic);for(int i=1;i<=Q;i++)printf("%d\n",ans[i]);if(ncase)putchar('\n');}return 0;
}

另外格式上---如果是case之间隔一个空行，最后一个case是不需要输出\n的，因为这个PE了

这篇关于hdu 4358 欧拉树形变线性+树状数组+离散化+离线+区间内出现k次的不同的数有几个+手动扩展栈的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---