数据结构（二）
2019-07-22 本文已影响0人
云中翻月
树状数组
POJ 1990: MooFest
关于x坐标建立树状数组。
先按照v值升序排序，逐个添加到树状数组里。
每次查询时统计现存的cow到当前cow的距离和，分为左右统计进入答案即可。
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
关于x坐标建立树状数组。
先按照v值升序排序，逐个添加到树状数组里。
每次查询时统计现存的cow到当前cow的距离和，分为左右统计进入答案即可。
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=20000+5;
const int INF=0x3f3f3f3f;
ll ans=0,c1[maxn],c2[maxn]; //c维护满足条件的cow的坐标和 c1维护满足条件的cow的个数
int n,maxx=0;
struct node{
ll x,v;
bool operator<(const node& h)const{return v<h.v;}
}a[maxn];
void add1(int x,ll v){
for(int i=x;i<=maxx;i+=i&-i) c1[i]+=v;
}
ll ask1(int x){
ll ans=0;
for(int i=x;i>=1;i-=i&-i) ans+=c1[i];
return ans;
}
void add2(int x){
for(int i=x;i<=maxx;i+=i&-i) c2[i]+=1;
}
ll ask2(int x){
ll ans=0;
for(int i=x;i>=1;i-=i&-i) ans+=c2[i];
return ans;
}
int main() {
ios::sync_with_stdio(false);
//freopen("MooFest.in","r",stdin);
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i].v>>a[i].x,maxx=max(maxx,(int)a[i].x);
sort(a+1,a+n+1);
for(int i=1;i<=n;i++){
ll sum1=ask1(a[i].x); //ask1(a[i].x)得到当前cow左侧的所有符合条件的奶牛的坐标和
ll sum2=ask2(a[i].x); //ask2(a[i].x)得到当前cow左侧符合条件的奶牛的个数
// D(sum);E;
// D(a[i].v*(a[i].x*(i-1)-sum));E;
ans+=a[i].v*((a[i].x*sum2-sum1)+((ask1(maxx)-sum1)-a[i].x*(i-1-sum2)));
add1(a[i].x,a[i].x);
add2(a[i].x);
}
cout<<ans;
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
POJ 3109: Inner Vertices
这题本来应该是扫描线+树状数组。但是我不会树状数组维护的扫描线，因此参照网上的写法实现的扫描线+线段树。
题解链接：https://blog.csdn.net/weizhuwyzc000/article/details
ps:
1 cin即使关闭流同步仍旧会超时。
2 这题我交了十几遍，全是RE。最后发现是这两个问题导致的。
build(rt<<1,l,mid);
写了成了
build(rt<<1,1,mid);
以及
if(mid>=l) ans+=sum(rt<<1,l,r);
if(mid<r) ans+=sum(rt<<1|1,l,r);
写了成了
if(mid>=l) ans+=sum(rt<<1,l,r);
if(mid<=r) ans+=sum(rt<<1|1,l,r);
尤其是第一个笔误，小数据根本不会RE，很难检查出来。
代码如下
/*
这题本来应该是扫描线+树状数组。但是我不会树状数组维护的扫描线，因此参照网上的写法实现的扫描线+线段树。
题解链接：https://blog.csdn.net/weizhuwyzc000/article/details/52460659
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=200005;
const int INF=0x3f3f3f3f;
struct SegmentTree {
int l,r,v; //支持单点修改 区间求和
} t[maxn<<2];
struct node {
int x,y;
bool operator<(const node& h)const {
return x==h.x?y<h.y:x<h.x; //按照x为主关键字排序 扫描线从下往上扫
}
} a[maxn];
int bx[maxn],by[maxn],cnt1,cnt2,n; //离散化数组
void build(int rt,int l,int r) {
t[rt].l=l,t[rt].r=r,t[rt].v=0;
if(l>=r) return;
int mid=l+r>>1;
build(rt<<1,l,mid);
build(rt<<1|1,mid+1,r);
}
void change(int rt,int x,int c) {
if(t[rt].l==t[rt].r) {
t[rt].v=c;
return;
}
int mid=t[rt].l+t[rt].r>>1;
if(mid>=x) change(rt<<1,x,c);
else change(rt<<1|1,x,c);
t[rt].v=t[rt<<1].v+t[rt<<1|1].v;
}
void update(int rt,int l,int r,int c) {
if(t[rt].l>=l&&t[rt].r<=r) {
t[rt].v=c;
return;
}
int mid=t[rt].l+t[rt].r>>1;
if(mid>=l) update(rt<<1,l,r,c);
if(mid<r) update(rt<<1|1,l,r,c);
t[rt].v=t[rt<<1].v+t[rt<<1|1].v;
}
int sum(int rt,int l,int r) {
if(t[rt].l>=l&&t[rt].r<=r) return t[rt].v;
int mid=t[rt].l+t[rt].r>>1;
int ans=0;
if(mid>=l) ans+=sum(rt<<1,l,r);
if(mid<r) ans+=sum(rt<<1|1,l,r);
return ans;
}
int table[maxn]= {0},p[maxn]={0}; //table[i]表示y坐标为i的最靠右的黑点的x坐标
int main() {
// ios::sync_with_stdio(false);
//freopen("Inner Vertices.in","r",stdin);
cin>>n;
/*
if(n==0||n==1||n==2||n==3){
cout<<n;return 0;
}
*/
for(int i=1; i<=n; i++) scanf("%d%d",&a[i].x,&a[i].y),bx[i]=a[i].x,by[i]=a[i].y;
sort(bx+1,bx+n+1);
cnt1=unique(bx+1,bx+n+1)-bx-1;
sort(by+1,by+n+1);
cnt2=unique(by+1,by+n+1)-by-1;
// D(cnt1);D(cnt2);E;
sort(a+1,a+n+1);
build(1,1,cnt2); //因为扫描线从下往上扫 所以关于y坐标建立线段树
for(int i=n; i>=1; i--) { //从右往左预处理table数组
int xx=lower_bound(bx+1,bx+cnt1+1,a[i].x)-bx;
int yy=lower_bound(by+1,by+cnt2+1,a[i].y)-by;
if(p[yy]) ;
else {
p[yy] = 1;
table[yy] = xx;
}
// if(!table[yy]) table[yy]=xx;
// D(xx);D(yy);D(table[yy]);E;
}
int ans=0;
for(int i=1; i<=n; i++) {
int xx=lower_bound(bx+1,bx+cnt1+1,a[i].x)-bx;
int yy=lower_bound(by+1,by+cnt2+1,a[i].y)-by;
// D(xx);D(yy);E;
// if(table[yy]==xx) change(1,yy,0); //如果已经是最靠右的点了 后面的扫描线不会在此处产生贡献 所以置为0
// else change(1,yy,1); //否则以后还会再在这个y坐标产生贡献 所以置为1
if(table[yy]>xx) update(1,yy,yy,1);
else update(1,yy,yy,0);
if(i==1||a[i].x!=a[i-1].x) continue; //如果前后x坐标不同 则竖线上无法产生黑点
int l=lower_bound(by+1,by+cnt2+1,a[i-1].y)-by; //每次在x坐标相同的相邻两个点之间的线段上产生贡献
int r=lower_bound(by+1,by+cnt2+1,a[i].y)-by; //r=yy
l++,r--; //除去两个端点
// D(l);D(r);E;
if(r>=l) ans+=sum(1,l,r); //如果两个端点之间还有点 就统计贡献
}
cout<<ans+n;
return 0;
}
示例.png
暴力做法是直接模拟修改矩形或者对于每个Q询问，遍历一遍前面所有的C询问，判断有多少C询问包括了这次Q询问的坐标。
下面对第二种暴力做法优化。
判断有多少C询问包括了这次Q询问的坐标，等价于，这次Q询问的坐标被C询问对应的矩形覆盖了多少次。
更具体地说，这次Q询问的坐标对应的答案就是覆盖次数&1。
为了高效的完成举行覆盖，将其转化为对四个角的操作。（类似前缀和操作，只不过坐标都+1了，如上图）
最后用二维树状数组维护这个操作序列即可。
ps：由于前面有下标+1的操作，所以n也要对应+1。
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
暴力做法是直接模拟修改矩形或者对于每个Q询问，遍历一遍前面所有的C询问，判断有多少C询问包括了这次Q询问的坐标。
下面对第二种暴力做法优化。
判断有多少C询问包括了这次Q询问的坐标，等价于，这次Q询问的坐标被C询问对应的矩形覆盖了多少次。
更具体地说，这次Q询问的坐标对应的答案就是覆盖次数&1。
为了高效的完成举行覆盖，将其转化为对四个角的操作。（类似前缀和操作，只不过坐标都+1了，如上图）
最后用二维树状数组维护这个操作序列即可。
ps：由于前面有下标+1的操作，所以n也要对应+1。
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=1000+5;
const int INF=0x3f3f3f3f;
int T,n,m,c[maxn][maxn];
void init(){
memset(c,0,sizeof(c));
}
void add(int x,int y,int d){
for(int i=x;i<=n;i+=i&-i) for(int j=y;j<=n;j+=j&-j) c[i][j]+=d;
}
int sum(int x,int y){
int ans=0;
for(int i=x;i>=1;i-=i&-i) for(int j=y;j>=1;j-=j&-j) ans+=c[i][j];
return ans;
}
int main() {
ios::sync_with_stdio(false);
//freopen("Matrix.in","r",stdin);
cin>>T;
while(T--){
cin>>n>>m;
n+=1;
init();
char op;
while(m--){
cin>>op;
if(op=='C'){
int X1,Y1,X2,Y2;
cin>>X1>>Y1>>X2>>Y2;
// X1++,Y1++,X2++,Y2++;
add(X1,Y1,1);add(X1,Y2+1,-1);add(X2+1,Y1,-1);add(X2+1,Y2+1,1);
}
else{
int x,y;
cin>>x>>y;
// x++,y++;
int val=sum(x,y);
// D(val);E;
int ans=val&1;
cout<<ans<<endl;
}
}
cout<<endl;
}
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
POJ 2886: Who Gets the Most Candies?
树状数组+二分维护序列的第k个1的位置。
题解链接 https://www.cnblogs.com/dybala21/p/10536771.html
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
树状数组+二分维护序列的第k个1的位置。
题解链接 https://www.cnblogs.com/dybala21/p/10536771.html
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=500000+5;
const int INF=0x3f3f3f3f;
char mp[maxn][20],ansp[20];
int n,k,c[maxn],f[maxn],a[maxn],ans; //f[i]表示i的约数个数
void pre(int n){
for(int i=1;i<=n;i++) for(int j=1;j<=n/i;j++) f[i*j]++;
}
void init(){
memset(c,0,sizeof(c));
ans=0;
}
void add(int x,int d){
for(int i=x;i<=n;i+=i&-i) c[i]+=d;
}
int sum(int x){
int ans=0;
for(int i=x;i>=1;i-=i&-i) ans+=c[i];
return ans;
}
int getpos(int num){
int l=1,r=n;
while(l<r){
int mid=l+r>>1;
if(sum(mid)<num) l=mid+1;
else r=mid;
}
return l;
}
void solve(){
int pos;
for(int i=1;i<=n;i++){ //枚举轮数i 当前圈大小为n-i
pos=getpos(k);
add(pos,-1);
if(f[i]>ans){
ans=f[i];
strcpy(ansp,mp[pos]);
}
if(a[pos]>0) k--; //顺时针存在补位的情况 所以需要-1
k=((k+a[pos])%(n-i)+n-i)%(n-i);
if(k==0) k=n-i; //树状数组不能维护第0个1的位置 所以要取模数的最大值
}
pos=getpos(k); //因为到了最后一个时 n-i=0 所以要独立出来判断
if(f[n]>ans){
ans=f[n];
strcpy(ansp,mp[pos]);
}
}
int main() {
// ios::sync_with_stdio(false);
//freopen("Who Gets the Most Candies.in","r",stdin);
pre(maxn-5);
while(cin>>n>>k){
init();
for(int i=1;i<=n;i++) add(i,1);
string s;int num;
for(int i=1;i<=n;i++) scanf("%s%d",mp[i],&num),a[i]=num;
solve();
cout<<ansp<<" "<<ans<<endl;
}
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
线段树和平方分割
POJ 3264: Balanced Lineup
维护区间最大值和最小值，模板题，ST表或者线段树均可。
这里提供线段树版本。（卡cin和cout很恶心）
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
维护区间最大值和最小值，模板题，ST表或者线段树均可。
这里提供线段树版本。（卡cin和cout很恶心）
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=50000+5;
const int INF=0x3f3f3f3f;
struct SegmentTree{
int l,r,mi,ma;
}tr[maxn<<2];
int n,q,a[maxn];
void build(int rt,int l,int r){
tr[rt].l=l,tr[rt].r=r;
if(l==r){
tr[rt].mi=tr[rt].ma=a[l];
return;
}
int mid=l+r>>1;
build(rt<<1,l,mid);
build(rt<<1|1,mid+1,r);
tr[rt].mi=min(tr[rt<<1].mi,tr[rt<<1|1].mi);
tr[rt].ma=max(tr[rt<<1].ma,tr[rt<<1|1].ma);
}
int query_max(int rt,int l,int r){
if(tr[rt].l>=l&&tr[rt].r<=r) return tr[rt].ma;
int mid=tr[rt].l+tr[rt].r>>1;
int ans=0;
if(mid>=l) ans=max(ans,query_max(rt<<1,l,r));
if(mid<r) ans=max(ans,query_max(rt<<1|1,l,r));
return ans;
}
int query_min(int rt,int l,int r){
if(tr[rt].l>=l&&tr[rt].r<=r) return tr[rt].mi;
int mid=tr[rt].l+tr[rt].r>>1;
int ans=INF;
if(mid>=l) ans=min(ans,query_min(rt<<1,l,r));
if(mid<r) ans=min(ans,query_min(rt<<1|1,l,r));
return ans;
}
int main() {
// ios::sync_with_stdio(false);
//freopen("Balanced Lineup.in","r",stdin);
cin>>n>>q;
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
build(1,1,n);
int A,B;
while(q--){
// cin>>A>>B;
scanf("%d%d",&A,&B);
// cout<<query_max(1,A,B)-query_min(1,A,B)<<endl;
printf("%d\n",query_max(1,A,B)-query_min(1,A,B));
}
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
POJ 3368: Frequent values
将连续的相同的数处理成一个个的块，对于每个块，用线段树维护其块中数字个数。
最后统计时像分块一样分成三个部分考虑即可。
恶心的是这题也卡了cin和cout。
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
将连续的相同的数处理成一个个的块，对于每个块，用线段树维护其块中数字个数。
最后统计时像分块一样分成三个部分考虑即可。
恶心的是这题也卡了cin和cout。
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=100000+5;
const int INF=0x3f3f3f3f;
struct SegmentTree{
int l,r,mi,ma;
}tr[maxn<<2];
int n,q,a[maxn],cnt,num[maxn]; //cnt为块数 num[i]表示第i个数所属的块的编号
struct node{
int l,r,cnt;
}p[maxn];
void init(){
cnt=1;
}
void build(int rt,int l,int r){
tr[rt].l=l,tr[rt].r=r;
if(l==r){
tr[rt].mi=tr[rt].ma=p[l].cnt;
return;
}
int mid=l+r>>1;
build(rt<<1,l,mid);
build(rt<<1|1,mid+1,r);
tr[rt].mi=min(tr[rt<<1].mi,tr[rt<<1|1].mi);
tr[rt].ma=max(tr[rt<<1].ma,tr[rt<<1|1].ma);
}
int query(int rt,int l,int r){
if(tr[rt].l>=l&&tr[rt].r<=r) return tr[rt].ma;
int mid=tr[rt].l+tr[rt].r>>1;
int ans=0;
if(mid>=l) ans=max(ans,query(rt<<1,l,r));
if(mid<r) ans=max(ans,query(rt<<1|1,l,r));
return ans;
}
void pre(){
p[1].l=1;num[1]=1;
for(int i=2;i<=n;i++){
if(a[i]!=a[i-1]){
p[cnt].r=i-1;
p[cnt].cnt=p[cnt].r-p[cnt].l+1;
p[++cnt].l=i;
}
num[i]=cnt;
// D(num[i]);
}
p[cnt].r=n;
p[cnt].cnt=p[cnt].r-p[cnt].l+1;
// for(int i=1;i<=cnt;i++){
// D(p[i].l);D(p[i].r);D(p[i].cnt);E;
// }
}
int main() {
// ios::sync_with_stdio(false);
//freopen("Frequent values.in","r",stdin);
while(cin>>n){
if(!n) break;
cin>>q;
init();
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
pre();
build(1,1,cnt);
int l,r,L,R;
while(q--){
cin>>l>>r;
int ans=0;
if(num[r]==num[l]) ans=r-l+1;
else{
int ans1=p[num[l]].r-l+1; //左边不完整的块
int ans2=r-p[num[r]].l+1; //右边不完整的块
L=num[l]+1,R=num[r]-1;
if(R>=L) ans=max(ans,query(1,L,R));
ans=max(ans,max(ans1,ans2));
}
printf("%d\n",ans);
}
}
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
POJ 3470: Walls
离散化一次处理所有数。
若鸟向左飞，将鸟和矩形左边都按x增序快排。扫描y线从左向右，将墙y范围内的线段树更新为墙id。
其他方向同理。最后按离散前距离差为每个鸟选择合适的方向，并更新对应计数器。
代码如下
/*
离散化一次处理所有数。
若鸟向左飞，将鸟和矩形左边都按x增序快排。扫描y线从左向右，将墙y范围内的线段树更新为墙id。
其他方向同理。最后按离散前距离差为每个鸟选择合适的方向，并更新对应计数器。
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=50000+5;
const int INF=0x3f3f3f3f;
struct wall{
int X1,Y1,X2,Y2;
}w[maxn];
struct bird{
int x,y,hit[6];
}b[maxn];
bool cmpx(const bird i,const bird j){
return i.x<j.x;
}
bool cmpy(const bird i,const bird j){
return i.y<j.y;
}
struct seg{
int a,b,c,id;
bool operator<(const seg& h)const{return c<h.c;}
}s[maxn];
struct SegmentTree{
int l,r,id; //id表示这一段区域属于哪一道墙
}tr[(maxn<<2)*6]; //maxn*6=maxn*4+maxn*2
int n,m,com[maxn*6],cnt=0,ans[maxn];
void build(int rt,int l,int r){
tr[rt].l=l,tr[rt].r=r,tr[rt].id=-1;
if(l==r) return;
int mid=l+r>>1;
build(rt<<1,l,mid);
build(rt<<1|1,mid+1,r);
}
void update(int rt,int l,int r,int c){
if(tr[rt].l>=l&&tr[rt].r<=r){
tr[rt].id=c;
return;
}
if(tr[rt].id!=-1){
tr[rt<<1].id=tr[rt<<1|1].id=tr[rt].id;
tr[rt].id=-1;
}
int mid=tr[rt].l+tr[rt].r>>1;
if(mid>=l) update(rt<<1,l,r,c);
if(mid<r) update(rt<<1|1,l,r,c);
}
int query(int rt,int x){
if(tr[rt].l==tr[rt].r||tr[rt].id!=-1) return tr[rt].id;
int mid=tr[rt].l+tr[rt].r>>1;
return mid>=x?query(rt<<1,x):query(rt<<1|1,x);
}
int main() {
// ios::sync_with_stdio(false);
//freopen("Walls.in","r",stdin);
cin>>n>>m;
for(int i=1;i<=n;i++){
scanf("%d%d%d%d",&w[i].X1,&w[i].Y1,&w[i].X2,&w[i].Y2);
if(w[i].X1>w[i].X2) swap(w[i].X1,w[i].X2); //X1<=X2
if(w[i].Y1>w[i].Y2) swap(w[i].Y1,w[i].Y2); //Y1<=Y2
com[++cnt]=w[i].X1;com[++cnt]=w[i].Y1;com[++cnt]=w[i].X2;com[++cnt]=w[i].Y2;
}
for(int i=1;i<=m;i++) scanf("%d%d",&b[i].x,&b[i].y),com[++cnt]=b[i].x,com[++cnt]=b[i].y;
//compress 离散化
sort(com+1,com+cnt+1);
cnt=unique(com+1,com+cnt+1)-com-1;
for(int i=1;i<=n;i++){
w[i].X1=lower_bound(com+1,com+cnt+1,w[i].X1)-com;
w[i].Y1=lower_bound(com+1,com+cnt+1,w[i].Y1)-com;
w[i].X2=lower_bound(com+1,com+cnt+1,w[i].X2)-com;
w[i].Y2=lower_bound(com+1,com+cnt+1,w[i].Y2)-com;
// D(w[i].X1);D(w[i].X2);D(w[i].Y1);D(w[i].Y2);E;
}
for(int i=1;i<=m;i++){
b[i].x=lower_bound(com+1,com+cnt+1,b[i].x)-com;
b[i].y=lower_bound(com+1,com+cnt+1,b[i].y)-com;
}
//扫描线垂直于x轴
for(int i=1;i<=n;i++){
s[i].a=w[i].Y1,s[i].b=w[i].Y2;
s[i].c=w[i].X1,s[i].id=i;
}
sort(s+1,s+n+1);
sort(b+1,b+m+1,cmpx);
//小鸟撞到左边的墙上
build(1,1,cnt);
int j=1;
for(int i=1;i<=m;i++){
for(;j<=n&&b[i].x>=s[j].c;j++) update(1,s[j].a,s[j].b,s[j].id);
b[i].hit[1]=query(1,b[i].y);
}
//小鸟撞到右边的墙上
build(1,1,cnt);
j=n;
for(int i=m;i>=1;i--){
for(;j>=1&&b[i].x<=s[j].c;j--) update(1,s[j].a,s[j].b,s[j].id);
b[i].hit[2]=query(1,b[i].y);
}
//扫描线垂直于y轴
for(int i=1;i<=n;i++){
s[i].a=w[i].X1,s[i].b=w[i].X2;
s[i].c=w[i].Y1,s[i].id=i;
}
sort(s+1,s+n+1);
sort(b+1,b+m+1,cmpy);
//小鸟撞到下边的墙上
build(1,1,cnt);
j=1;
for(int i=1;i<=m;i++){
for(;j<=n&&b[i].y>=s[j].c;j++) update(1,s[j].a,s[j].b,s[j].id);
b[i].hit[3]=query(1,b[i].x);
}
//小鸟撞到上边的墙上
build(1,1,cnt);
j=n;
for(int i=m;i>=1;i--){
for(;j>=1&&b[i].y<=s[j].c;j--) update(1,s[j].a,s[j].b,s[j].id);
b[i].hit[4]=query(1,b[i].x);
}
//比较hit[i]，判断小鸟最终会撞到哪堵墙
for(int i=1;i<=m;i++){
int id=-1,dis=-1;
for(int j=1;j<=4;j++){
int tid=b[i].hit[j];
if(tid!=-1){
int tmp;
if(j==1) tmp=abs(com[b[i].x]-com[w[tid].X2]); //鸟向左撞
if(j==2) tmp=abs(com[b[i].x]-com[w[tid].X1]); //鸟向右撞
if(j==3) tmp=abs(com[b[i].y]-com[w[tid].Y2]); //鸟向下撞
if(j==4) tmp=abs(com[b[i].y]-com[w[tid].Y1]); //鸟向上撞
if(tmp<dis||dis==-1){
dis=tmp;id=tid;
}
}
}
ans[id]++;
}
for(int i=1;i<=n;i++) printf("%d\n",ans[i]);
return 0;
}
POJ 1201: Intervals
贪心，把输入的区间按照右端点从小到大排序，每次查询当前区间内的点是否已经足够。
若不够则从区间右边开始取点，直至恰好满足该区间所要求的点数。
实现的时候用线段树。
ps：由于最多有50000个点，所以单点修改操作最多进行50000次，在时间复杂度允许范围内。
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
贪心，把输入的区间按照右端点从小到大排序，每次查询当前区间内的点是否已经足够。
若不够则从区间右边开始取点，直至恰好满足该区间所要求的点数。
实现的时候用线段树。
ps：由于最多有50000个点，所以单点修改操作最多进行50000次，在时间复杂度允许范围内。
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=50000+5;
const int INF=0x3f3f3f3f;
struct node{
int l,r,c;
bool operator<(const node& h)const{return r<h.r;}
}a[maxn];
struct SegmentTree{
int l,r,sum;
}tr[maxn<<2];
int n,vis[maxn],ans=0;
void build(int rt,int l,int r){
tr[rt].l=l,tr[rt].r=r,tr[rt].sum=0;
if(l==r) return;
int mid=l+r>>1;
build(rt<<1,l,mid);
build(rt<<1|1,mid+1,r);
}
void change(int rt,int x,int v){
if(tr[rt].l==tr[rt].r){
tr[rt].sum=v;return;
}
int mid=tr[rt].l+tr[rt].r>>1;
if(mid>=x) change(rt<<1,x,v);
else change(rt<<1|1,x,v);
tr[rt].sum=tr[rt<<1].sum+tr[rt<<1|1].sum;
}
int query(int rt,int l,int r){
if(tr[rt].l>=l&&tr[rt].r<=r) return tr[rt].sum;
int mid=tr[rt].l+tr[rt].r>>1;
int ans=0;
if(mid>=l) ans+=query(rt<<1,l,r);
if(mid<r) ans+=query(rt<<1|1,l,r);
return ans;
}
int main() {
// ios::sync_with_stdio(false);
//freopen("Intervals.in","r",stdin);
cin>>n;
for(int i=1;i<=n;i++) scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].c);
sort(a+1,a+n+1);
build(1,1,maxn-5);
for(int i=1;i<=n;i++){
int left=a[i].c-query(1,a[i].l,a[i].r);
if(left<=0) continue;
int pos=a[i].r;
ans+=left;
while(left){
if(!vis[pos]){
vis[pos]=1;
change(1,pos,1);
left--;
}
pos--;
}
}
cout<<ans;
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
