Blog is given life again…..

C++ Source Lib File

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cctype>
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define fr(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout)
using namespace std;
const int maxn=1e5+10;
int a[maxn],n,m;
int upper_bound(int*,int,int,int);
int lower_bound(int*,int,int,int);
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	sort(a+1,a+n+1);
	scanf("%d",&m);
	while(m--)
	{
		int l,r,val;
		scanf("%d%d%d",&l,&r,&val);
		printf("upper_bound:%d\n",upper_bound(a,l,r,val));
		printf("lower_bound:%d\n",lower_bound(a,l,r,val));
	}
	return 0;
}
int upper_bound(int *num,int L,int R,int value)
{
	int count=R-L+1,pos,step;
	while(count>0)
	{
		pos=L,step=count>>1,pos+=step;
		if(value>=num[pos]) L=++pos,count-=step+1;
		else count=step;
	}
	return L;
}
int lower_bound(int *num,int L,int R,int value)
{
	int count=R-L+1,pos,step;
	while(count>0)
	{
		pos=L,step=count>>1,pos+=step;
		if(value>num[pos]) L=++pos,count-=step+1;
		else count=step;
	}
	return L;
}

def upper_bound(nums, value):  
    L,R=0,len(nums)-1
    count,pos,step=R-L+1,0,0
    while count > 0:
        pos,step=L,count>>1
        pos+=step
        if value>=nums[pos]:
            pos+=1
            L=pos
            count-=step+1
        else:
            count=step
    return L
def lower_bound(nums, value):  
    L,R=0,len(nums)-1
    count,pos,step=R-L+1,0,0
    while count > 0:
        pos,step=L,count>>1
        pos+=step
        if value>nums[pos]:
            pos+=1
            L=pos
            count-=step+1
        else:
            count=step
    return L

立个flag，四个月没学OI，用4天遍历一遍版……

SegTree

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define fr(x) freopen(#x ".in","r",stdin);freopen(#x ".out","w",stdout)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int maxn=1e5+10;
typedef long long ll;
typedef ll LL[maxn<<1];
LL sum,add;
int n;
void build(int,int,int);
void update(int,int,int,int,int,int);
void PushUP(int);
void PushDown(int,int);
ll query(int,int,int,int,int);
int main()
{
	//fr();
	
	//fprintf(stderr,"Times : %.2f s\n",clock()*1.0/CLOCK_PER_SEC);
	return 0;
}
void build(int l,int r,int rt)
{
	add[rt]=0;
	if(l==r)
	{
		scanf("%lld",&sum[rt]);
		return;
	}
	int m=(l+r)>>1;
	build(lson),build(rson);
	PushUP(rt);
}
void update(int L,int R,int val,int l,int r,int rt)
{
	if(L<=l&&r<=R)
	{
		add[rt]+=val;
		sum[rt]+=1ll*(r-l+1)*val;
		return;
	}
	PushDown(rt,r-l+1);
	int m=(l+r)>>1;
	if(L<=m) update(L,R,val,lson);
	if(R>m) update(L,R,val,rson);
	PushUP(rt);
}
ll query(int L,int R,int l,int r,int rt)
{
	if(L<=l&&r<=R) return sum[rt];
	PushDown(rt,r-l+1);
	int m=(l+r)>>1;ll ret=0;
	if(L<=m) ret+=query(l,r,lson);
	if(R>m) ret+=query(l,r,rson);
	return ret;
}
void PushUP(int rt)
{
	sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void PushDown(int rt,int m)
{
	if(add[rt])
	{
		add[rt<<1]+=add[rt],add[rt<<1|1]+=add[rt];
		sum[rt<<1]+=add[rt]*(m-(m>>1)),sum[rt<<1|1]+=add[rt]*(m>>1);
		add[rt]=0;
	}
}