HNCU专题训练_线段树（1）
2024-10-20 08:49:33
1.内存控制
2.敌兵布阵
4.广告牌
5.区间第k大数(模板题)
6.just a Hook
7.I Hate It
8.动态的最长递增子序列(区间更新题)
9.图灵树
10.覆盖的面积
14.买票问题
16.村庄问题
17.Hotel
19.矩形周长问题
23.区间第k大数问题
26.海报问题
1001
/* 内存控制
4种操作：
1.Reset 初始化
2.New x 开辟长度为x的连续的空间，输出起始位置
3.Free x 释放包含第x字节的块，整块都释放掉
4.Get x 输出当前状态下，内存里第x块的起始位置 思路：
1.Reset 很简单，update(1,N,EMPTY,1);就可以了
没有必要重新构树 2.New x 对于这个操作，和Hotel这道题是一样的。
建立树的过程中保存了lmax,rmax,max。在查询的
过程中有一些小的技巧。 3.Free x 释放内存，开一个容器，维护这个容器的顺序。
学到了很多容器的知识。海，以前没有学过容器
还是学别人的。
4.Get x 也是通过维护这个容器，来得到的。 详细的见代码 */ #include<cstdio>
#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<vector>
#define EMPTY 2 //纯色 此题中代表 空的。
#define HH 1 //混色 此题中代表 被占用了。
using namespace std; struct node
{
int l;
int r;
int lmax,rmax,max;
int len;
int color;
}f[*];
struct st
{
int begin;
int end;
};
vector<st>tom; int hmax(int x,int y)
{
return x>y? x:y;
} bool cmp1(st n1,st n2)
{
return n1.begin<n2.begin;
} void build(int l,int r,int n) //建树。
{
int mid=(l+r)/;
f[n].l=l;
f[n].r=r;
f[n].color=;
f[n].len=f[n].r-f[n].l+;
f[n].lmax=f[n].rmax=f[n].max=f[n].len;
if(l==r)
return;
build(l,mid,n*);
build(mid+,r,n*+);
}
/*
建设的过程也有一个小小的亮点，可以把
f[n].lmax=f[n].rmax=f[n].max=f[n].len;
用向上更新来写在build(mid+1,r,n*2+1)后,带上
*/ void make_down(int n) //向下更新
{
if(f[n].color==EMPTY)
{
f[n*].max=f[n*].rmax=f[n*].lmax=f[n*].len;
f[n*+].max=f[n*+].rmax=f[n*+].lmax=f[n*+].len;
}
else if(f[n].color==HH)
{
f[n*].max=f[n*].lmax=f[n*].rmax=;
f[n*+].max=f[n*+].lmax=f[n*+].rmax=;
} f[n*].color=f[n].color;
f[n*+].color=f[n].color; f[n].color=;
f[n].lmax=f[n].rmax=f[n].max=; } void make_up(node *father,node *l_child,node *r_child) //向上更新
{
father->lmax=(l_child->lmax==l_child->len)? l_child->lmax+r_child->lmax: l_child->lmax;
father->rmax=(r_child->rmax==r_child->len)? r_child->rmax+l_child->rmax: r_child->rmax;
father->max=hmax(hmax(father->lmax,father->rmax),
hmax(l_child->max,
hmax(r_child->max,l_child->rmax+r_child->lmax)));
}
//为什么这道题，有个小小的亮点，没有rnum ,lnum；
//仔细一想确实是不需要的.. void update(int l,int r,int num,int n) //更新函数 区间[l,r]，更新为num。
{
int mid=(f[n].l+f[n].r)/;
if(f[n].l==l && f[n].r==r)
{
if(num==EMPTY)
{
f[n].lmax=f[n].rmax=f[n].max=f[n].len;
}
else f[n].lmax=f[n].rmax=f[n].max=;
f[n].color=num;
return;
} if(f[n].color!=)
make_down(n);
if(mid>=r)
update(l,r,num,n*);
else if(mid<l)
update(l,r,num,n*+);
else
{
update(l,mid,num,n*);
update(mid+,r,num,n*+);
}
make_up(&f[n],&f[n*],&f[n*+]);
} int query(int max,int n)
{
int cur=; if(f[n].l==f[n].r)
return f[n].l;
if(f[n].color!=) //刚开始，这个别丢了，居然Running time error。
make_down(n); if(f[n*].max>=max)
cur=query(max,n*); else if(f[n*].rmax+f[n*+].lmax>=max)
return f[n*].r-f[n*].rmax+; else if(f[n*+].max>=max)
cur=query(max,n*+); make_up(&f[n],&f[n*],&f[n*+]);
return cur;
}
/*
刚开始 左子树，
然后是 左子树右边最大值+右子树左边最大值
最后才是 右子树
*/ void make_ini(int N,int M)
{
char a[];
int x,l,r,tmp;
st hxl;
while(M--)
{
scanf("%s",a);
if(a[]=='R')
{
update(,N,EMPTY,);
tom.clear();
printf("Reset Now\n");
}
if(a[]=='N')
{
scanf("%d",&x);
if(f[].max<x)
{
printf("Reject New\n");
}
else
{
l=query(x,);
r=l+x-;
hxl.begin=l;
hxl.end=r;
vector<st>::iterator it;
it=upper_bound(tom.begin(),tom.end(),hxl,cmp1);//二分查找，前提是有序。
tom.insert(it,hxl);
printf("New at %d\n",l);
update(l,r,HH,);
}
}
else if(a[]=='F')
{
scanf("%d",&x);
hxl.begin=x;
hxl.end=x;
vector<st>::iterator it;//容器的使用啊
it=upper_bound(tom.begin(),tom.end(),hxl,cmp1); tmp=it-tom.begin()-;
if(tmp==- || tom[tmp].end<x)
printf("Reject Free\n");
else
{
printf("Free from %d to %d\n",tom[tmp].begin,tom[tmp].end);
update(tom[tmp].begin,tom[tmp].end,EMPTY,);
tom.erase(tom.begin()+tmp);
}
}
else if(a[]=='G')
{
scanf("%d",&x);
if(x>tom.size())
printf("Reject Get\n");
else
printf("Get at %d\n",tom[x-].begin);//容器的下标也是从0开始，所以要减1
}
}
} int main()
{
int N,M;
while(scanf("%d%d",&N,&M)>)
{
tom.clear();//这个必须要的。
build(,N,);
make_ini(N,M);
printf("\n"); //！！
}
return ;
}
1002
#include<stdio.h>
#include<iostream>
#include<cstdlib>
using namespace std; struct st
{
int l;
int r;
int num;
}f[*];
int date[]; void build(int l,int r,int n)
{
int mid=(l+r)/;
f[n].l=l;
f[n].r=r;
if(l==r)
{
f[n].num=date[l];
return ;
}
build(l,mid,n*);
build(mid+,r,n*+);
f[n].num=f[n*].num+f[n*+].num;
} void update(int wz,int num,int n)
{
int mid=(f[n].l+f[n].r)/;
if(f[n].l==wz && f[n].r==wz)
{
if(f[n].num+num<)
f[n].num=;
else f[n].num+=num;
return ;
}
if(wz<=mid)
update(wz,num,n*);
else
update(wz,num,n*+);
f[n].num=f[n*].num+f[n*+].num;
} int query(int l,int r,int n)
{
int sum=,mid=(f[n].l+f[n].r)/;
if(f[n].l==l && f[n].r==r)
{
sum+=f[n].num;
return sum;
}
if(mid<l)
sum+=query(l,r,n*+);
else if(mid>=r)
sum+=query(l,r,n*);
else
{
sum+=query(l,mid,n*);
sum+=query(mid+,r,n*+);
}
return sum; }
void makeini(int n,int T)
{
int i,j,k,l,r,wz,num;
char a[];
for(i=;i<=n;i++)
scanf("%d",&date[i]);
build(,n,);
scanf("%s",a);
while(a[]!='E')
{
if(a[]=='Q')
{
if(T>)
{
printf("Case %d:\n",T);
T=;
}
scanf("%d%d",&l,&r);
printf("%d\n",query(l,r,));
}
else if(a[]=='A')
{
scanf("%d%d",&wz,&num);
update(wz,num,);
}
else if(a[]=='S')
{
scanf("%d%d",&wz,&num);
update(wz,-num,);
}
scanf("%s",a);
}
} int main()
{
int T,n,i;
while(scanf("%d",&T)>)
{
for(i=;i<=T;i++)
{
scanf("%d",&n);
makeini(n,i);
}
}
return ;
}
1004
/*
我把query()写成这样，错了。不懂... int query(int max,int n)
{
int mid=(f[n].l+f[n].r)/2,sum=-1; if(f[n].l==f[n].r)
{
f[n].max=f[n].max-max;
return f[n].l;
}
if(f[n*2].max>=max)
sum= query(max,n*2);
else if(f[n*2+1].max>=max)
sum= query(max,n*2+1);
f[n].max=hxlmax(f[n*2].max,f[n*2+1].max);
return sum;
} */
#include<stdio.h>
#include<iostream>
#include<cstdlib>
using namespace std; struct st
{
int l;
int r;
int max;
}f[*];
int H,W,N; void build(int l,int r,int n)
{
int mid=(l+r)/;
f[n].l=l;
f[n].r=r;
if(l==r)
{
f[n].max=W;
return;
}
build(l,mid,n*);
build(mid+,r,n*+);
f[n].max=f[n*].max>f[n*+].max? f[n*].max:f[n*+].max;
} int query(int max,int n)
{
int mid=(f[n].l+f[n].r)/,sum=-; if(f[n].l==f[n].r)
{
f[n].max=f[n].max-max;
return f[n].l;
}
if(f[n*].max>=max)
sum= query(max,n*);
else if(f[n*+].max>=max)
sum= query(max,n*+);
f[n].max=f[n*].max>f[n*+].max? f[n*].max:f[n*+].max;
return sum;
} int main()
{
int wi,i;
while(scanf("%d%d%d",&H,&W,&N)>)
{
if(H>N)
H=N;
build(,H,);
while(N--)
{
scanf("%d",&wi);
if(wi>f[].max)
printf("-1\n");
else
printf("%d\n",query(wi,));
}
}
return ;
}
1005
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#define N 100010
using namespace std; int toleft[][N];
int Tree[][N];
int Sort[N]; void build(int l,int r,int dep)
{
int mid=(l+r)/,sum=mid-l+,lpos,rpos,i;
if(l==r) return ;
for(i=l;i<=r;i++)
if(Tree[dep][i]<Sort[mid]) sum--;
lpos=l;
rpos=mid+;
for(i=l;i<=r;i++)
{
if(Tree[dep][i]<Sort[mid])
{
Tree[dep+][lpos++]=Tree[dep][i];
}
else if(Tree[dep][i]==Sort[mid] && sum>)
{
Tree[dep+][lpos++]=Tree[dep][i];
sum--;
}
else
{
Tree[dep+][rpos++]=Tree[dep][i];
}
toleft[dep][i]=toleft[dep][l-]+lpos-l;
}
build(l,mid,dep+);
build(mid+,r,dep+);
} int query(int L,int R,int l,int r,int dep,int k)
{
int mid=(L+R)/,newl,newr,cur;
if(l==r) return Tree[dep][l];
cur=toleft[dep][r]-toleft[dep][l-];
if(cur>=k)
{
newl=L+toleft[dep][l-]-toleft[dep][L-];
newr=newl+cur-;
return query(L,mid,newl,newr,dep+,k);
}
else
{
newr=r+(toleft[dep][R]-toleft[dep][r]);//r的位置后移了
newl=newr-(r-l-cur);
return query(mid+,R,newl,newr,dep+,k-cur);
}
} void sc(int n)
{
int i,j;
for(j=;j<=;j++)
{
printf("\n");
for(i=;i<=;i++)
printf("%d ",Tree[j][i]);
}
} int main()
{
int T,n,m,i,l,r,k;
scanf("%d",&T);
{
while(T--)
{
scanf("%d%d",&n,&m);
memset(Tree,,sizeof(Tree));
for(i=;i<=n;i++)
{
scanf("%d",&Tree[][i]);
Sort[i]=Tree[][i];
}
sort(Sort+,Sort++n);
build(,n,);
while(m--)
{
scanf("%d%d%d",&l,&r,&k);//求区间[l,r]中第k大的数字
printf("%d\n",query(,n,l,r,,k));
}
// sc(n);
} }
return ;
}
/* 学长的模板
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string.h> using namespace std; #define N 100010 int sorted[N]; //排序完的数组
int toleft[30][N]; //toleft[i][j]表示第i层从1到k有多少个数分入左边
int tree[30][N]; //表示每层每个位置的值 void buildingTree(int l,int r,int dep)
{
if(l==r) return;
int mid = (l+r)>>1;
int i,sum = mid-l+1; //表示等于中间值而且被分入左边的个数
for(i=l;i<=r;i++)
{
if(tree[dep][i]<sorted[mid]) sum--;
}
int lpos=l;
int rpos=mid+1;
for(i=l;i<=r;i++)
{
if(tree[dep][i]<sorted[mid]) //比中间的数小，分入左边
{
tree[dep+1][lpos++]=tree[dep][i];
}
else if(tree[dep][i]==sorted[mid]&&sum>0) //等于中间的数值，分入左边，直到sum==0后分到右边
{
tree[dep+1][lpos++]=tree[dep][i];
sum--;
}
else //右边
{
tree[dep+1][rpos++]=tree[dep][i];
}
toleft[dep][i] = toleft[dep][l-1] + lpos - l; //从1到i放左边的个数
}
buildingTree(l,mid,dep+1);
buildingTree(mid+1,r,dep+1);
} //查询区间第k大的数，[L,R]是大区间，[l,r]是要查询的小区间
int queryTree(int L,int R,int l,int r,int dep,int k)
{
if(l==r) return tree[dep][l];
int mid = (L+R)>>1;
int cnt = toleft[dep][r] - toleft[dep][l-1]; //[l,r]中位于左边的个数
if(cnt>=k)
{
int newl = L + toleft[dep][l-1] - toleft[dep][L-1]; //L+要查询的区间前被放在左边的个数
int newr = newl + cnt - 1; //左端点加上查询区间会被放在左边的个数
return queryTree(L,mid,newl,newr,dep+1,k);
}
else
{
int newr = r + toleft[dep][R] - toleft[dep][r];
int newl = newr - (r - l - cnt);
return queryTree(mid+1,R,newl,newr,dep+1,k-cnt);
}
} int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n,m,i;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
{
scanf("%d",&tree[0][i]);
sorted[i] = tree[0][i];
}
sort(sorted+1,sorted+1+n);
buildingTree(1,n,0);
while(m--)
{
int s,t,k;
scanf("%d%d%d",&s,&t,&k);
printf("%d\n",queryTree(1,n,s,t,0,k));
}
}
return 0;
}*/
1006
/* 线段树延迟标记，感觉自己的方法不是很好。
color==0 表示是纯色的，
color==HH 表示是混色的。 很久没有写线段树了...
*/ #include<stdio.h>
#include<iostream>
#include<cstdlib>
#define HH -1
using namespace std; struct st
{
int l;
int r;
int color;
int num;
}f[*]; void build(int l,int r,int n)
{
int mid=(l+r)/;
f[n].l=l;
f[n].r=r;
f[n].color=;
f[n].num=;
if(l==r) return ;
build(l,mid,n*);
build(mid+,r,n*+);
} void updown(int n)
{
f[n*].color=;
f[n*+].color=;
f[n].color=HH;
f[n*].num=f[n].num;
f[n*+].num=f[n].num;
} void update(int l,int r,int size,int n)
{
int mid=(f[n].l+f[n].r)/;
if(f[n].l==l && f[n].r==r)
{
f[n].color=;//纯色
f[n].num=size;
return ;
}
if(f[n].color==)
updown(n);
if(mid<l)
update(l,r,size,n*+);
else if(mid>=r)
update(l,r,size,n*);
else
{
update(l,mid,size,n*);
update(mid+,r,size,n*+);
}
} int query(int l,int r,int n)
{
int mid=(f[n].l+f[n].r)/,sum=;
if(f[n].l==l && f[n].r==r && f[n].color==)
{
return f[n].num*(f[n].r-f[n].l+);
}
if(f[n].color==)
updown(n);
if(mid>=r)
sum+=query(l,r,n*);
else if(mid<l)
sum+=query(l,r,n*+);
else
{
sum+=query(l,mid,n*);
sum+=query(mid+,r,n*+);
}
return sum;
} int main()
{
int T,i,n,Q,l,r,size;
while(scanf("%d",&T)>)
{
for(i=;i<=T;i++)
{
scanf("%d",&n);
build(,n,);
scanf("%d",&Q);
while(Q--)
{
scanf("%d%d%d",&l,&r,&size);
update(l,r,size,);
}
printf("Case %d: The total value of the hook is %d.\n",i,query(,n,));
}
}
return ;
}
1007
/* 水题 */ #include<stdio.h>
#include<iostream>
#include<cstdlib>
using namespace std; struct st
{
int l;
int r;
int max;
}f[*];
int date[]; void build(int l,int r,int n)
{
int mid=(l+r)/;
f[n].l=l;
f[n].r=r;
if(l==r)
{
f[n].max=date[l];
return;
}
build(l,mid,n*);
build(mid+,r,n*+);
f[n].max=f[n*].max>f[n*+].max? f[n*].max:f[n*+].max;
} void update(int wz,int num,int n)
{
int mid=(f[n].l+f[n].r)/;
if(f[n].l==wz && f[n].r==wz)
{
f[n].max=num;
return;
}
if(wz<=mid)
update(wz,num,n*);
else if(wz>mid)
update(wz,num,n*+);
f[n].max=f[n*].max>f[n*+].max? f[n*].max:f[n*+].max;
} int query(int l,int r,int n)
{
int mid=(f[n].l+f[n].r)/,max,a,b;
if(f[n].l==l && f[n].r==r)
{
return f[n].max;
}
if(mid>=r)
max=query(l,r,n*);
else if(mid<l)
max=query(l,r,n*+);
else
{
a=query(l,mid,n*);
b=query(mid+,r,n*+);
max=a>b? a:b;
}
return max;
} int main()
{
int i,N,M,l,r,wz,num;
char a[];
while(scanf("%d%d",&N,&M)>)
{
for(i=;i<=N;i++)
scanf("%d",&date[i]);
build(,N,);
for(i=;i<=M;i++)
{
scanf("%s",a);
if(a[]=='Q')
{
scanf("%d%d",&l,&r);
printf("%d\n",query(l,r,));
}
else if(a[]=='U')
{
scanf("%d%d",&wz,&num);
update(wz,num,);
}
}
}
return ;
}
1008
#include<stdio.h>
#include<iostream>
#include<cstdlib>
using namespace std; struct st
{
int l,r,lnum,rnum;
int lmax,rmax,max;
int len;
}f[*];
int date[]; int hxlmax(int x,int y)
{
return x>y? x:y;
} void make_up(st *father, st *l_child, st *r_child)
{
father->lnum=l_child->lnum;
father->rnum=r_child->rnum;
if(l_child->rnum>=r_child->lnum)
{
father->lmax=l_child->lmax;
father->rmax=r_child->rmax;
father->max =hxlmax(l_child->max,r_child->max);
}
else
{
father->lmax=(l_child->lmax==l_child->len)? l_child->lmax+r_child->lmax: l_child->lmax;
father->rmax=(r_child->rmax==r_child->len)? r_child->rmax+l_child->rmax: r_child->rmax;
father->max =hxlmax(hxlmax(father->lmax,father->rmax),l_child->rmax+r_child->lmax);
}
} void build(int l,int r,int n)
{
int mid=(l+r)/;
f[n].l=l;
f[n].r=r;
f[n].len=f[n].r-f[n].l+;
if(l==r)
{
f[n].lnum=date[l];
f[n].rnum=date[l];
f[n].lmax=;
f[n].rmax=;
f[n].max=;
return;
}
build(l,mid,n*);
build(mid+,r,n*+);
make_up(&f[n],&f[n*],&f[n*+]);
} void update(int wz,int num,int n)
{
int mid=(f[n].l+f[n].r)/;
if(f[n].l==wz && f[n].r==wz)
{
f[n].lnum=num;
f[n].rnum=num;
return ;
}
if(mid>=wz)
update(wz,num,n*);
else if(mid<wz)
update(wz,num,n*+);
make_up(&f[n],&f[n*],&f[n*+]);
} int query(int l,int r,int n)
{ }
void make_ini(int n,int m)
{
int i,l,r,wz,num;
char a[];
for(i=;i<=n;i++)
scanf("%d",&date[i]);
build(,n,);
while(m--)
{
scanf("%s",a);
if(a[]=='Q')
{
scanf("%d%d",&l,&r);
printf("%d\n",query(++l,++r,));
}
else if(a[]=='U')
{
scanf("%d%d",&wz,&num);
update(++wz,num,);
}
}
}
int main()
{
int T,n,m;
while(scanf("%d",&T)>)
{
while(T--)
{
scanf("%d%d",&n,&m);
make_ini(n,m);
}
}
return ;
}
1009
/*
hdu3333
题意：给你一段很长的数字，求区间[l,r]里的和，满足数字重复出现的，只能算一次。 测试数据10组，
N 30000; 数字大小10^9；Q 10^5; 用数组保存要询问的区间，离线算法..
Next[]求出下一个重复出现数字的位置 对x排序，用线段树更新max值。 对初始的询问位置排序，输出结果。 */
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<map>
using namespace std; struct st
{
int l;
int r;
__int64 max;
}f[*];
struct node
{
int begin;
int end;
__int64 max;
int wz;
}b[];
int a[];
int tom[];
int Next[]; map<int,int>hxl; bool cmp1(node n1,node n2) //起始位置从小到大排
{
return n1.begin<n2.begin;
} bool cmp2(node n1,node n2) //back
{
return n1.wz<n2.wz;
} void build(int l,int r,int n)
{
int mid=(l+r)/;
f[n].l=l;
f[n].r=r;
if(l==r)
{
f[n].max=tom[l];
return;
}
build(l,mid,n*);
build(mid+,r,n*+);
f[n].max=f[n*].max+f[n*+].max;
} void update(int wz,int num,int n)
{
int mid=(f[n].l+f[n].r)/;
if(f[n].l==wz && f[n].r==wz)
{
f[n].max=num;
return;
}
if(mid>=wz)
update(wz,num,n*);
else if(mid<wz)
update(wz,num,n*+);
f[n].max=f[n*].max+f[n*+].max;
} __int64 query(int l,int r,int n)
{
int mid=(f[n].l+f[n].r)/;
if(f[n].l==l && f[n].r==r)
{
return f[n].max;
}
if(mid>=r)
return query(l,r,n*);
else if(mid<l)
return query(l,r,n*+);
else
{
return query(l,mid,n*)+query(mid+,r,n*+);
}
} void make_then(int N,int Q)
{
int i,j,k;
for(i=;i<=N;i++)
{
tom[i]=;
Next[i]=;
}
hxl.clear();
for(i=N;i>=;i--)
{
k=a[i];
if(hxl.find(k)==hxl.end())
{
hxl[k]=i;
}
else
{
Next[i]=hxl[k];
hxl[k]=i;
}
}// get Next[]
hxl.clear();
for(i=;i<=N;i++)
{
k=a[i];
if(hxl.find(k)==hxl.end())
{
tom[i]=k;
hxl[k]=i;
}
}// get tom[]
} void cs(int N,int Q)
{
int i,j;
for(i=;i<=N;i++)
printf("%d ",Next[i]);
printf("\n\n");
for(i=;i<=N;i++)
printf("%d ",tom[i]);
printf("\n");
} void make_ini()
{
int Q,N,i,j,k,l,r;
scanf("%d",&N);
for(i=;i<=N;i++)
scanf("%d",&a[i]);
scanf("%d",&Q);
for(i=;i<=Q;i++)
{
scanf("%d%d",&b[i].begin,&b[i].end);
b[i].wz=i;
b[i].max=;
}
sort(b+,b++Q,cmp1);
make_then(N,Q);
// cs(N,Q);
build(,N,);
k=;
for(i=;i<=Q;i++)
{
l=b[i].begin;
r=b[i].end;
if(k<l)
{
for(j=k;j<l;j++)
{
if(Next[j]>)
update(Next[j],a[j],);
}
k=l;
}
b[i].max=query(l,r,);
}
sort(b+,b++Q,cmp2);
for(i=;i<=Q;i++)
printf("%I64d\n",b[i].max);
} int main()
{
int T;
scanf("%d",&T);
{
while(T--)
{
make_ini();
}
}
return ;
}
1010
/*
初学切割线，看陈俊学长的博客，
感觉他的代码写得很漂亮。
*/ #include<cstdio>
#include<iostream>
#include<cstdlib>
#include<algorithm>
using namespace std; struct Line
{
double x;
double y1;
double y2;
int flag;
}line[];
struct node
{
int l;
int r;
double x;
double y1,y2;
int cover;
}f[*];
double YY[]; bool cmp(Line n1,Line n2)
{
return n1.x<n2.x;
} void build(int l,int r,int n)
{
int mid=(l+r)/;
f[n].l=l;
f[n].r=r;
f[n].y1=YY[l];
f[n].y2=YY[r];
f[n].x=;
f[n].cover=;
if(l+==r) return;
build(l,mid,n*);
build(mid,r,n*+);
} double update(Line cur,int n)
{
double now; if(cur.y1>=f[n].y2 || cur.y2<=f[n].y1) return ;
if(f[n].l+==f[n].r)
{
if(f[n].cover<)
{
f[n].cover+=cur.flag;
f[n].x=cur.x;
return ;
}
else
{
now=(f[n].y2-f[n].y1)*(cur.x-f[n].x);
f[n].cover+=cur.flag;
f[n].x=cur.x;
return now;
}
}
return (update(cur,n*)+update(cur,n*+));
} void cs(int len)
{
int i;
for(i=;i<=len;i++)
printf("%.3lf ",line[i].x);
printf("\n"); for(i=;i<=len;i++)
printf("%.3lf ",YY[i]);
printf("\n"); } void make_ini(int N)
{
int i,len=;
double x1,y1,x2,y2,cur=;
for(i=;i<=N;i++)
{
scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
line[++len].x=x1;
line[len].y1=y1;
line[len].y2=y2;
line[len].flag=; YY[len]=y1;
YY[++len]=y2; line[len].x=x2;
line[len].y1=y1;
line[len].y2=y2;
line[len].flag=-;
}
sort(YY+,YY++len);
sort(line+,line++len,cmp);
build(,len,);
//把这个建树放在了，两个sort之前，果断不对，检查N time
// cs(len);
for(i=;i<=len;i++)
{
cur+=update(line[i],);
}
printf("%.2lf\n",cur); } int main()
{
int T,N;
while(scanf("%d",&T)>)
{
while(T--)
{
scanf("%d",&N);
make_ini(N);
}
}
return ;
}
1014
/*
买票问题
n个信息，
x val，表示，价值为val的人，前面有x个人。
..... 最后输出最终的顺序 */
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<algorithm>
using namespace std; struct node
{
int l;
int r;
int max;
}f[*];
int Date[];
struct st
{
int begin;
int val;
}hxl[]; void build(int l,int r,int n)
{
int mid=(l+r)/;
f[n].l=l;
f[n].r=r;
f[n].max=f[n].r-f[n].l+;
if(l==r)
return ;
build(l,mid,n*);
build(mid+,r,n*+);
} int query(int max,int n)
{
int cur=;
if(f[n].l==f[n].r && f[n].max==max)
{
f[n].max=;
return f[n].l;
}
if(f[n*].max>=max)
cur=query(max,n*); else if(f[n*+].max>=max-f[n*].max)
cur=query(max-f[n*].max,n*+); f[n].max=f[n*].max+f[n*+].max;
return cur;
} int main()
{
int N;
int wz,i;
while(scanf("%d",&N)>)
{
build(,N,);
for(i=;i<=N;i++)
{
scanf("%d%d",&hxl[i].begin,&hxl[i].val);
}
for(i=N;i>=;i--)
{
wz=query(hxl[i].begin+,);
Date[wz]=hxl[i].val;
}
for(i=;i<=N;i++)
{
if(i==)
printf("%d",Date[i]);
else printf(" %d",Date[i]);
if(i==N)printf("\n");
}
}
return ;
}
1019
/*
统计周长
*/ #include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define N 5003
#define hxl 10003
using namespace std; struct node
{
int begin;
int end;
int val;
int flag;
}Linex[N<<],Liney[N<<];
int Hash[]; bool cmp(node n1,node n2)
{
return n1.val<n2.val;
} int make_x(int NN)
{
int sum=,i,j;
for(i=;i<=NN;i++)
{
if(Linex[i].flag==)
{
for(j=Linex[i].begin;j<Linex[i].end;j++)
{
if(Hash[j]==)
sum++;
Hash[j]++;
}
}
else
{
for(j=Linex[i].begin;j<Linex[i].end;j++)
{
if(Hash[j]==)
sum++;
Hash[j]--;
} }
}
return sum;
} int make_y(int NN)
{
int sum=,i,j;
for(i=;i<=NN;i++)
{
if(Liney[i].flag==)
{
for(j=Liney[i].begin;j<Liney[i].end;j++)//不取等
{
if(Hash[j]==)
sum++;
Hash[j]++;
}
}
else
{
for(j=Liney[i].begin;j<Liney[i].end;j++)
{
if(Hash[j]==)
sum++;
Hash[j]--;
}
}
}
return sum;
} void make_ini(int NN)
{
int x1,y1,x2,y2,i,len=,sum=;
for(i=;i<=NN;i++)
{
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
x1+=hxl;y1+=hxl;y2+=hxl;x2+=hxl; Linex[++len].val=x1;
Linex[len].begin=y1;
Linex[len].end=y2;
Linex[len].flag=; Liney[len].val=y1;
Liney[len].begin=x1;
Liney[len].end=x2;
Liney[len].flag=; Linex[++len].val=x2;
Linex[len].begin=y1;
Linex[len].end=y2;
Linex[len].flag=-; Liney[len].val=y2;
Liney[len].begin=x1;
Liney[len].end=x2;
Liney[len].flag=-;
}
sort(Linex+,Linex++len,cmp);
sort(Liney+,Liney++len,cmp);
memset(Hash,,sizeof(Hash));
sum+=make_x(len);
memset(Hash,,sizeof(Hash));
sum+=make_y(len);
printf("%d\n",sum);
} int main()
{
int NN;
while(scanf("%d",&NN)>)
{
make_ini(NN);
}
return ;
}
1023
和第5题一样的。
1026
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define HH 1//纯色
using namespace std; struct node
{
int l;
int r;
int num;
int color;
}f[*];
struct st
{
int l;
int r;
}a[];
int hxl[],hlen;
int tom[],tlen;
bool Hash[]; int EF(int l,int r,int num)
{
int mid=(l+r)/;
while(l<r)
{
if(hxl[mid]>num)
r=mid-;
else if(hxl[mid]<num)
l=mid+;
else if(hxl[mid]==num)
return mid;
mid=(l+r)/;
}
return mid;
} void build(int l,int r,int n)
{
int mid=(l+r)/;
f[n].l=l;
f[n].r=r;
f[n].num=;
f[n].color=;
if(l==r)
{
// f[n].color=HH;
return;
}
build(l,mid,n*);
build(mid+,r,n*+);
} void make_down(int n)
{
f[n*].color=f[n*+].color=HH;
f[n].color=; f[n*].num=f[n*+].num=f[n].num;
f[n].num=;
} void update(int l,int r,int num,int n)
{
int mid=(f[n].l+f[n].r)/;
if(f[n].l==l && f[n].r==r)
{
f[n].color=HH;
f[n].num=num;
return ;
}
if(f[n].color==HH)
make_down(n);
if(mid>=r)
update(l,r,num,n*);
else if(mid<l)
update(l,r,num,n*+);
else
{
update(l,mid,num,n*);
update(mid+,r,num,n*+);
}
} void query(int l,int r,int n)
{
int mid=(f[n].l+f[n].r)/;
if(f[n].l==l && f[n].r==r)
{
if(f[n].color==HH && f[n].num>)
{
Hash[f[n].num]=true;
return ;
}
}
if(f[n].l==f[n].r) return;
if(f[n].color==HH)
make_down(n);
if(mid>=r)
query(l,r,n*);
else if(mid<l)
query(l,r,n*+);
else
{
query(l,mid,n*);
query(mid+,r,n*+);
}
return ;
} void make_ini(int n)
{
int i,l,r,max=;
tlen=;
for(i=;i<=n;i++)
{
scanf("%d%d",&a[i].l,&a[i].r);
tom[++tlen]=a[i].l;
tom[++tlen]=a[i].r;
}
sort(tom+,tom++tlen);
memset(Hash,false,sizeof(Hash));
hxl[]=tom[];
hlen=;
for(i=;i<=tlen;i++)
{
if(tom[i]!=tom[i-])
hxl[++hlen]=tom[i];
}
build(,hlen,);
for(i=;i<=n;i++)
{
l=EF(,hlen,a[i].l);
r=EF(,hlen,a[i].r);
update(l,r,i,);
}
query(,hlen,);
for(i=;i<=n;i++)
if(Hash[i]==true)
max++;
printf("%d\n",max); } void sc()
{
int i;
for(i=;i<=tlen;i++)
printf("%d ",tom[i]);
printf("\n"); for(i=;i<=hlen;i++)
printf("%d ",hxl[i]);
printf("\n"); } int main()
{
int T,n;
while(scanf("%d",&T)>)
{
while(T--)
{
scanf("%d",&n);
make_ini(n);
// sc();
}
}
return ;
}
最新文章
- visual studio 工具的使用
- [java] jsoup 解析网页获取省市区域信息
- Images.xcassets
- Android 常见工具类封装
- 【Hadoop代码笔记】Hadoop作业提交之Job初始化
- 《UNIX环境高级编程》学习心得 二
- sql 游标循环当中重新赋值
- wince下sources\sources.cmn\Makefile.def的相关作用
- linux日志审计项目案例实战（生产环境日志审计项目解决方案）
- IceMx.Mvc 我的js MVC 框架 三、动手来写一个评论模块儿
- easyui小清新俺也晒晒 视频管理软件bs项目
- javascript apply()和call()
- NOIP2016提高组初赛（C++语言）试题 个人的胡乱分析
- Orcle查询优化改写-----给查询结果排序
- OpenStack-Glance（3）
- Doracle.jdbc.J2EE13Compliant=true
- [Python]基础教程（2）、PyCharm安装及中文编码
- 安装clickhouse缺少依赖libicudata.so.50()(64bit)
- BZOJ3523[Poi2014]Bricks——贪心+堆
- 3-D models provided some resources
热门文章
- Mac OS 10.12 - 安装Homebrew，像Ubuntu里面的apt一样简单地安装和删除软件！
- 队列（循环队列）----C语言
- RabbitMQ Java实例
- 【学习笔记】linux bash script
- ThreadLocal的实现机制
- JDK1.10+scala环境的搭建之linux环境（centos6.9）
- (win 7)使用puma以后，重启rails server报错： in `trap': unsupported signal SIGCHLD (ArgumentError)
- 【数组】Rotate Image
- 用PopupWindow做下拉框
- 三篇文章了解 TiDB 技术内幕 - 说存储(转)