【ツリー配列】特集+テンプレート
9103 ワード
テンプレートを先に置く...
私も書きたいと思っています.
しかしidの値はジャンプする可能性があり、例えば上のr[]={1,3,5,2,4}は、3番目のdp[5][j]+=dp 1[4][j-1]と計算されるが、この場合はまだdp 1[4][]の値がないため、加算できない.このとき,樹状配列の役割が現れる.
【接頭辞とkの下付き位置を求め、sum()と正反対】
【POJ 2155】 http://poj.org/problem?id=21552 Dマトリクスツリー配列(区間を修正し、点の値を求める)
【POJ 2299】隣接する要素を少なくとも数回交換して数列をインクリメントすることを求める(木配列でできるとは考えにくい)http://poj.org/problem?id=2299
http://blog.csdn.net/lyy289065406/article/details/6647346
本質はバブルソートですが、集計ソートで解くこともできます.のhttp://www.cnblogs.com/gj-Acit/archive/2013/08/10/3250525.html
【POJ3321】 http://poj.org/problem?id=3321(修正点、区間値を求める)
(題意転)リンゴの木を1本あげます.木の主幹を1にします.それぞれの枝を1つの数にします.Nまで、このリンゴの木を表します.それぞれの枝の上には最大1つのリンゴしかありません.つまり、1つの枝の上に2つのリンゴがあるはずがありません.また、リンゴの木を2つのフォークの木と想像しないでください.リンゴの木はノードごとに多くのフォークを分けることができます.多叉木
入力はフォークの関係で、
1 2
1 3
主幹の上の2つのフォークはそれぞれ2と3です.
次は2つの操作で、QとC
C jの意味は、jという枝の上にリンゴがあれば摘み、なければ新しいものが生えてくるということです
Q jはjというフォークの上のりんごの総数を聞くことです.
http://www.cnblogs.com/Jason-Damon/archive/2012/03/02/2376471.html
hdu3450 lower_bound離散化大数値http://acm.hdu.edu.cn/showproblem.php?pid=3450
いくつかの数をあげて、どれだけの集合があるかを聞いて、隣接する数の間の差を満たす絶対値はdより小さいです.
hdu 5592は配列a[]を与え、a[i]はb[]の前のi個数の逆順序対個数を表し、この配列b[]を復元する.http://acm.hdu.edu.cn/showproblem.php?pid=5592
#define lowbit(x) (x) & (-x)
const int N=1005;
const int M=1e9+7;
//【 （ ）， （ ）】の
int dp[N][N],c[NN][N];
int a[N],r[N],w[N];
bool cmp(int b,int c) {
return a[b]<a[c];
}
void update(int i,int j,int value){
while(i<=NN){ // NN （N*2 ）
c[i][j]=(c[i][j]+value%M)%M;
i+=lowbit(i);
}
}
int sum(int i,int j){ //i <=0，
int s=0;
while(i>0){
s=(s+c[i][j])%M;
i-=lowbit(i);
}
return s%M;
}
int main(){
int t,cnt=0;
cin>>t;
while(t--){
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
scanf("%d",&a[i]);
memset(c,0,sizeof(c));
memset(dp,0,sizeof(dp));
for(int i=0;i<=n;++i)
r[i]=i; //
sort(r+1,r+n+1,cmp); // a[]
for(int i=1;i<=n;++i)
w[r[i]]=i; // a[] （ 400,500,600 1,2,3）
for(int i = 1; i <= n; ++i) {
dp[w[i]][1]=1;
update(w[i],1,1);
for(int j=2;j<=m;++j) {
dp[w[i]][j]=sum(w[i]-1,j-1); // w i w[i] j-1 ， Σdp[k][j-1](1<=k<w[i])
update(w[i], j, dp[w[i]][j]);// dp[w[i]][j]
}
}
int ans = 0;
//for(int i=1;i<=n;++i) ans=(ans+dp[i][m])%M; ， sum(n,m)
printf("Case #%d: %d
",++cnt,sum(n,m) % M);
}
return 0;
}私も書きたいと思っています.
for(int j=2;j<=m;++j){
dp[id][j]=dp1[id-1][j-1];
dp1[id][j]+=dp1[id-1][j];
}しかしidの値はジャンプする可能性があり、例えば上のr[]={1,3,5,2,4}は、3番目のdp[5][j]+=dp 1[4][j-1]と計算されるが、この場合はまだdp 1[4][]の値がないため、加算できない.このとき,樹状配列の役割が現れる.
【接頭辞とkの下付き位置を求め、sum()と正反対】
int find(int k){
int cnt = 0, ans = 0;
for (int i = 20; i >= 0; --i){ //2^20 50000
ans += (1 << i);
if (ans >= n || cnt + c1[ans] >= k) ans -= (1 << i);
else cnt += c1[ans];
}
return ans+1;
}void update2(int ii,int val){ //
w[ii]=val;
for(int i=ii; i<=n+5; i+=lowbit(i)){
if(val>c2[i])
c2[i]=val;
else
break;
}
}
int query(int l, int r){
int s=w[r];//
while (l!=r){
for(r-=1;r-lowbit(r)>=l;r-=lowbit(r)){
s=max(s,c2[r]);// ，
}
s=max(s,w[r]); //
}
return s;
} 【POJ 2155】 http://poj.org/problem?id=21552 Dマトリクスツリー配列(区間を修正し、点の値を求める)
const int N=1005,NN=3000;
const int M=1e9+7;
int dp[N][N],c1[NN][NN];
int n,m,a,b,c,d;
void update(int ii,int jj,int val){ // （ ）
for(int i=ii; i>0; i-=lowbit(i)){
for(int j=jj; j>0; j-=lowbit(j)){
c1[i][j]=(c1[i][j]+val);
}
}
}
int sum(int ii,int jj){ // （ ）
int s=0;
for(int i=ii; i<=NN; i+=lowbit(i)){
for(int j=jj; j<=NN; j+=lowbit(j)){
s+=c1[i][j];
}
}
return s;
}
int main(){
int t;
scanf("%d",&t);
while(t--){
memset(c1,0,sizeof(c1));
char cc[2];
scanf("%d%d",&n,&m);
for(int i=0;i<m;++i){
scanf("%s",&cc);
if(cc[0]=='C'){
scanf("%d%d%d%d",&a,&b,&c,&d);
a++;b++;c++;d++;
update(a-1,b-1,1);
update(a-1,d,-1);
update(c,b-1,-1);
update(c,d,1);
}
else{
scanf("%d%d",&a,&b);
a++;b++;
printf("%d
",sum(a,b)%2);
}
}
printf("
");
}
return 0;
}【POJ 2299】隣接する要素を少なくとも数回交換して数列をインクリメントすることを求める(木配列でできるとは考えにくい)http://poj.org/problem?id=2299
http://blog.csdn.net/lyy289065406/article/details/6647346
本質はバブルソートですが、集計ソートで解くこともできます.のhttp://www.cnblogs.com/gj-Acit/archive/2013/08/10/3250525.html
const int N=500005,NN=1500005;
const int M=1e9+7;
ll c1[NN];
int n,m;
ll a;
void update(ll ii,ll val){ //
for(int i=ii; i<=NN; i+=lowbit(i)){
c1[i]=(c1[i]+val);
}
}
int sum(ll ii){ //
ll s=0;
for(int i=ii; i>0; i-=lowbit(i)){
s+=c1[i];
}
return s;
}
int main(){
int n;
while(cin>>n&&n){
memset(c1,0,sizeof(c1));
ll s=0;
for(int i=0;i<n;++i){
cin>>a;
a++;
s+=i-sum(a-1);
update(a,1);
}
cout<<s<<endl;
}
return 0;
} 【POJ3321】 http://poj.org/problem?id=3321(修正点、区間値を求める)
(題意転)リンゴの木を1本あげます.木の主幹を1にします.それぞれの枝を1つの数にします.Nまで、このリンゴの木を表します.それぞれの枝の上には最大1つのリンゴしかありません.つまり、1つの枝の上に2つのリンゴがあるはずがありません.また、リンゴの木を2つのフォークの木と想像しないでください.リンゴの木はノードごとに多くのフォークを分けることができます.多叉木
入力はフォークの関係で、
1 2
1 3
主幹の上の2つのフォークはそれぞれ2と3です.
次は2つの操作で、QとC
C jの意味は、jという枝の上にリンゴがあれば摘み、なければ新しいものが生えてくるということです
Q jはjというフォークの上のりんごの総数を聞くことです.
http://www.cnblogs.com/Jason-Damon/archive/2012/03/02/2376471.html
const int N=100005,NN=300005;
const int M=1e9+7;
int c1[NN];
vector<vector<int> > v(N);
//vector<int> v[N]; ？？
int f;
int y[N],st[N],ed[N];
void update(int ii,int val){
for(int i=ii; i<=NN; i+=lowbit(i)){
c1[i]=(c1[i]+val);
}
}
int sum(int ii){
int s=0;
for(int i=ii; i>0; i-=lowbit(i)){
s+=c1[i];
}
return s;
}
void dfs(int p){ // ， （ ）
st[p]=++f;
for(int i=0;i<v[p].size();++i){
dfs(v[p][i]);
}
ed[p]=f;
}
int main(){
int n,a,b;
scanf("%d",&n);
for(int i=0;i<n-1;++i){
scanf("%d %d",&a,&b);
v[a].push_back(b);
}
f=1; // 2
dfs(1);
int m;
scanf("%d",&m);
for(int i=0;i<m;++i){
char c[2];
scanf("%s %d",c,&a);
if(c[0]=='C'){
if(y[a]==0){
update(st[a],-1);
y[a]=1;
}
else{
update(st[a],1);
y[a]=0;
}
}
else if(c[0]=='Q'){
printf("%d
",sum(ed[a])-sum(st[a]-1)+ed[a]-st[a]+1); //
}
}
return 0;
} hdu3450 lower_bound離散化大数値http://acm.hdu.edu.cn/showproblem.php?pid=3450
いくつかの数をあげて、どれだけの集合があるかを聞いて、隣接する数の間の差を満たす絶対値はdより小さいです.
const int N=100005,NN=300005;
int x[N],y[N];
int c1[NN];
void update(int ii,int val){ //
for(int i=ii; i<=NN; i+=lowbit(i)){
c1[i]=(c1[i]+val)%9901;
}
}
int sum(int ii){ //
int s=0;
for(int i=ii; i>0; i-=lowbit(i)){
s=(s+c1[i])%9901;
}
return s;
}
int main(){
int n,m;
while(scanf("%d%d",&n,&m)==2){
memset(c1,0,sizeof c1);
for(int i=1;i<=n;++i){
scanf("%d",&x[i]);
y[i]=x[i];
}
sort(y+1,y+n+1); // y ，
for(int i=1;i<=n;++i){
int p=lower_bound(y+1,y+n+1,x[i]-m)-y; //
int q=upper_bound(y+1,y+n+1,x[i]+m)-y-1; //
//【 ！！ a-b ((a-b)%mod+mod)%mod， 】
int s=((sum(q+1)-sum(p-1+1))%9901+9901)%9901;
int h=lower_bound(y+1,y+n+1,x[i])-y;
update(h+1,(s+1)%9901);
}
printf("%d
",((sum(n+1)-(n%9901))%9901+9901)%9901);
}
return 0;
} hdu 5592は配列a[]を与え、a[i]はb[]の前のi個数の逆順序対個数を表し、この配列b[]を復元する.http://acm.hdu.edu.cn/showproblem.php?pid=5592
const int N=50005,NN=50005;
int x[N];
int y[N],z[N],w[N];
int c1[NN],c2[NN];
int n;
void update(int ii,int val){ //
for(int i=ii; i<=n+5; i+=lowbit(i)){
c1[i]=(c1[i]+val);
}
}
int find(int k){ //【 k 。 sum() 】
int cnt = 0, ans = 0;
for (int i = 20; i >= 0; --i){ //2^20 50000
ans += (1 << i);
if (ans >= n || cnt + c1[ans] >= k) ans -= (1 << i);
else cnt += c1[ans];
}
return ans+1;
}
int main(){
int t;
scanf("%d",&t);
while(t--){
memset(c1,0,sizeof(c1));
memset(z,0,sizeof(z));
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d",&x[i]);
update(i,1);
}
for(int i=n;i>=2;--i){
int p=x[i]-x[i-1];
y[i]=find(i-p);
update(y[i],-1);
z[y[i]]=1;
}
for(int i=1;i<=n;++i){
if(z[i]==0)
y[1]=i;
}
for(int i=1;i<=n-1;++i)
printf("%d ",y[i]);
printf("%d
",y[n]);
}
return 0;
}