【线段树/树状数组】数星星

青旅半醒 2024-03-23 16:42 64阅读 0赞

**这是板子题，但是想记录一下，因为想警醒自己写线段树的时候注意l和r的范围，是从0开始的还是1开始的，否则就直接RE！**

**如果给的数据是0开始的就直接手动++**

**namo总是注意不到这一点**

**namo还是写的太少了**

[1012-数星星 Stars\_2021秋季算法入门班第十一章习题：线段树、树状数组 (nowcoder.com)][1012-_ Stars_2021_ _nowcoder.com]

题意：

![0984679d6e794fcab129658703e39b9b.png][]

Code：（树状数组）

#include <bits/stdc++.h>
    
    //#define int long long
    #define low(x) (x&(-x))
    
    using namespace std;
    
    const int mxn=4e4+10;
    const int mxe=4e4+10; 
    const int Inf=1e9;
    
    map<int,int> mp;
    
    int N,x,y;
    int x_mx=4e4;
    int tree[mxe<<2];
    
    void add(int x,int k){
    	for(int i=x;i<=x_mx;i+=low(i)) tree[i]+=k;
    }
    int sum(int x){
    	int res=0;
    	for(int i=x;i;i-=low(i)) res+=tree[i];
    	return res;
    }
    void solve(){
    	cin>>N;
    	for(int i=1;i<=N;i++){
    		cin>>x>>y;
    		x++,y++;
    		mp[sum(x)]++;
    		add(x,1);
    	}
    	for(int i=0;i<=N-1;i++) cout<<mp[i]<<'\n';
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;//cin>>__;
    	while(__--)solve();return 0;
    }

Code：（线段树）

#include <bits/stdc++.h>
    
    //#define int long long
    
    using namespace std;
    
    const int mxn=4e4+10;
    const int mxe=4e4+10; 
    const int Inf=1e9;
    
    struct ty{
    	int val;
    }tree[mxe<<2];
    
    map<int,int> mp;
    
    int N,x,y,x_mx=4e4;
    
    void pushup(int rt){
    	tree[rt].val=tree[rt<<1].val+tree[rt<<1|1].val;
    }
    int query(int rt,int l,int r,int x,int y){
    	if(x<=l&&r<=y){
    		return tree[rt].val;
    	}
    	int mid=l+r>>1;
    	int res=0;
    	if(x<=mid) res+=query(rt<<1,l,mid,x,y);
    	if(y>mid) res+=query(rt<<1|1,mid+1,r,x,y);
    	return res;
    }
    void modify(int rt,int l,int r,int x,int k){
    	if(l==r){
    		tree[rt].val+=k;
    		return;
    	}
    	int mid=l+r>>1;
    	if(x<=mid) modify(rt<<1,l,mid,x,k);
    	else modify(rt<<1|1,mid+1,r,x,k);
    	pushup(rt);
    }
    void build(int rt,int l,int r){
    	if(l==r){
    		tree[rt].val=0;
    		return;
    	}
    	int mid=l+r>>1;
    	build(rt<<1,l,mid);
    	build(rt<<1|1,mid+1,r);
    	pushup(rt);
    }
    void solve(){
    	cin>>N;
    	build(1,1,x_mx);
    	for(int i=1;i<=N;i++){
    		cin>>x>>y;
    		x++,y++;
    		mp[query(1,1,x_mx,1,x)]++;
    		modify(1,1,x_mx,x,1); 
    	}
    	for(int i=0;i<=N-1;i++) cout<<mp[i]<<'\n'; 
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;//cin>>__;
    	while(__--)solve();return 0;
    }

[1012-_ Stars_2021_ _nowcoder.com]: https://ac.nowcoder.com/acm/contest/26896/1012
[0984679d6e794fcab129658703e39b9b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/9fa02d12fcb94ab9ace0724737411dfa.png