扫描线
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=4e5+10;
int read(){
int x=0,f=1;char c=getchar();
while(c>'9' || c<'0'){if(c=='-')f=-1;c=getchar();}
while(c>='0' && c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
return x*f;
}
struct LINE{
int l,r,y,va;
bool operator<(const LINE &t1)const{
return y<t1.y;
}
}line[N];
struct TREE{
int l,r,va,lazy;
}e[N<<2];
int tot,n,X[N],ans;
int x,y,xx,yy;
void pushup(int u){
if(e[u].lazy)e[u].va=X[e[u].r+1]-X[e[u].l];
else e[u].va=e[u<<1].va+e[u<<1|1].va;
return;
}
void build(int u,int l,int r){
e[u].l=l,e[u].r=r;if(l==r)return;
int mid=l+r>>1;build(u<<1,l,mid);build(u<<1|1,mid+1,r);
return;
}
void update(int u,int L,int R,int add){
if(L>X[e[u].r+1] || R<=X[e[u].l])return;
if(L<=X[e[u].l] && X[e[u].r+1]<=R){
e[u].lazy+=add;
pushup(u);
return;
}
update(u<<1,L,R,add);
update(u<<1|1,L,R,add);
pushup(u);
return;
}
signed main(){
n=read();
for(int i=1;i<=n;i++){
x=read(),y=read();xx=read(),yy=read();
X[2*i-1]=x,X[2*i]=xx;
line[2*i-1]=(LINE){x,xx,y,1},line[2*i]=(LINE){x,xx,yy,-1};
}
n<<=1;sort(line+1,line+n+1);sort(X+1,X+n+1);
tot=unique(X+1,X+n+1)-X-1;
build(1,1,tot-1);
for(int i=1;i<n;i++){
update(1,line[i].l,line[i].r,line[i].va);
ans+=(line[i+1].y-line[i].y)*e[1].va;
}
printf("%lld\n",ans);
return 0;
}
线段树
#include<bits/stdc++.h>
using namespace std;
const int N=201000;
int read(){
int x=0,f=1;char c=getchar();
while(c>'9' || c<'0'){
if(c=='-')f=-1;
c=getchar();
}
while(c>='0' && c<='9'){
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
struct node{
int l,r,va,lazy;
}e[N<<2];
int a[N],Q,n,opt,L,R,V;
void pushup(int p){
e[p].va=max(e[p<<1].va,e[p<<1|1].va);
return;
}
void pushdown(int p){
e[p<<1].lazy+=e[p].lazy;
e[p<<1|1].lazy+=e[p].lazy;
e[p<<1].va+=e[p].lazy;
e[p<<1|1].va+=e[p].lazy;
e[p].lazy=0;
return;
}
void build(int p,int l,int r){
e[p].l=l,e[p].r=r;
if(l==r){
e[p].va=a[l];return;
}
int m=l+r>>1;
build(p<<1,l,m);
build(p<<1|1,m+1,r);
pushup(p);
return;
}
void update(int p,int l,int r,int v){
if(l<=e[p].l && r>=e[p].r){
e[p].va+=v;
e[p].lazy+=v;
return;
}
pushdown(p);
int mid=e[p].l+e[p].r>>1;
if(l<=mid)updata(p<<1,l,r,v);
if(r>mid)updata(p<<1|1,l,r,v);
pushup(p);
return;
}
int query(int p,int l,int r){
if(l<=e[p].l && r>=e[p].r){
return e[p].va;
}
int mid=e[p].l+e[p].r>>1;
pushdown(p);
int ans=0;
if(l<=mid)ans=qurey(p<<1,l,r);
if(r>mid)ans=max(ans,qurey(p<<1|1,l,r));
return ans;
}
int main()
{
n=read();Q=read();
for(int i=1;i<=n;i++)a[i]=read();
build(1,1,n);
while(Q--){
opt=read();
if(opt==1){
L=read(),R=read(),V=read();
update(1,L,R,V);
}
else{
L=read(),R=read();
printf("%d\n",query(1,L,R));
}
}
return 0;
}
值域+动态开点（时间复杂度没有离散化好）
TIP:如果是区间修改，pushdown时也要新开点（query时要推lazy）
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=1000100;
ll read()
{
ll x=0,f=1;char c=getchar();
while(c>'9' || c<'0'){
if(c=='-')f=-1;
c=getchar();
}
while(c>='0' && c<='9'){
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
struct node{
ll l,r,va;
}e[N<<2];
ll n,tot,ans,cnt,root,L[N],R[N];
ll a[N];
void pushup(ll u){
e[u].va=e[L[u]].va+e[R[u]].va;
return;
}
void updata(ll &u,ll l,ll r,ll key){
if(!u){
u=++cnt;
e[u].l=l,e[u].r=r;
e[u].va=0;
}
if(l==r && l==key){
e[u].va++;
return;
}
ll mid=l+r>>1;
if(key<=mid)updata(L[u],l,mid,key);
if(key>mid)updata(R[u],mid+1,r,key);
pushup(u);
return;
}
ll qurey(ll u,ll l,ll r){
if(!u)return 0;
if(l<=e[u].l && e[u].r<=r)return e[u].va;
ll mid=e[u].l+e[u].r>>1;
ll res=0;
if(l<=mid)res+=qurey(L[u],l,r);
if(r>mid)res+=qurey(R[u],l,r);
return res;
}
int main()
{
n=read();
for(ll i=1;i<=n;i++)a[i]=read(),tot=max(tot,a[i]);
for(ll i=1;i<=n;i++){
updata(root,1,tot,a[i]);
ans+=qurey(root,a[i]+1,tot);
}
printf("%lld",ans);
return 0;
}
值域+离散化
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=100100;
struct none{
ll l,r,va;
}e[N<<2];
ll read()
{
ll x=0,f=1;char c=getchar();
while(c>'9' || c<'0'){
if(c=='-')f=-1;
c=getchar();
}
while(c>='0' && c<='9'){
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
ll n,tot,ans;
struct node{
ll wz,va;
}a[N],b[N];
bool cmp(node x,node y){
return x.va<y.va;
}
bool cmp2(node x,node y){
return x.wz<y.wz;
}
void pushup(ll u){
e[u].va=e[u<<1].va+e[u<<1|1].va;
return;
}
void build(ll u,ll l,ll r){
e[u].l=l,e[u].r=r;
if(l==r)return;
ll mid=e[u].l+e[u].r>>1;
build(u<<1,l,mid);
build(u<<1|1,mid+1,r);
return;
}
void updata(ll u,ll l,ll r){
if(e[u].l==e[u].r){
e[u].va++;
return;
}
ll m=e[u].l+e[u].r>>1;
if(l<=m)updata(u<<1,l,r);
if(r>m)updata(u<<1|1,l,r);
pushup(u);
return;
}
ll qurey(ll u,ll l,ll r){
if(l<=e[u].l && e[u].r<=r)return e[u].va;
ll m=e[u].l+e[u].r>>1;
ll res=0;
if(l<=m)res+=qurey(u<<1,l,r);
if(r>m)res+=qurey(u<<1|1,l,r);
return res;
}
int main()
{
a[0].va=1000000000+1;
n=read();
for(ll i=1;i<=n;i++)a[i].va=read(),a[i].wz=i;
sort(a+1,a+n+1,cmp);
for(ll i=1;i<=n;i++){
if(a[i].va!=a[i-1].va)tot++;
b[i].va=tot;
b[i].wz=a[i].wz;
}
sort(b+1,b+n+1,cmp2);
build(1,1,tot);
for(ll i=1;i<=n;i++){
updata(1,b[i].va,b[i].va);
ans+=qurey(1,b[i].va+1,tot);
}
printf("%lld",ans);
return 0;
}
线段树合并
int Merge(int a,int b){
if(!a) return b;
if(!b) return a;
if(e[a].l==e[a].r){
e[a].va+=e[b].va;
return a;
}
int mid=(e[a].l+e[a].r)>>1;
e[a].ls=Merge(e[a].ls,e[b].ls);
e[a].rs=Merge(e[a].rs,e[b].rs);
pushup(a);
return a;
}
merge时要注意必须已经有a存在。 必要时写一个newnode函数 1 将树上每个点开一可棵权值线段树。 然后两点之间比较谁放前面 再向上合并 比较时只用比较alson乘brson与arson与blson
线段树分裂
int split(int &k,int x,int y){
int n=++cnt;
if(x<=l && y>=r){
e[n]=e[k];
k=0;
return n;
}
int mid=(e[k].l+e[k].r)>>1;
if(x<=m)e[n].l=split(e[k].l,x,y);
if(y>m)e[n].r=split(e[k].r,x,y);
pushup(k);
pushup(n);
return n;
}
空间2 * max(最大询问数字) * log2(线段树最大大小)
树剖
void dfs1(int u,int fat,int _h){
h[u]=_h;
size[u]=1;
fa[u]=fat;
for(int i=head[u];i;i=last[i]){
if(to[i]==fat)continue;
dfs1(to[i],u,_h+1);
size[u]+=size[to[i]];
if(size[to[i]]>size[maxson[u]])maxson[u]=to[i];
}
return;
}
void dfs2(int u,int _top){
top[u]=_top;
dfs[u]=++cnt;
RX[cnt]=u;
if(maxson[u])dfs2(maxson[u],_top);
for(int i=head[u];i;i=last[i]){
if(to[i]==fa[u] || to[i]==maxson[u])continue;
dfs2(to[i],to[i]);
}
return;
}
node Q(int x,int y){
node t1;t1.sum=0,t1.maxn=INT_MIN;
while(top[x]!=top[y]){
if(h[top[x]]<h[top[y]])swap(x,y) ;
t1.maxn=max(t1.maxn,query(1,dfs[top[x]],dfs[x]).maxn);
t1.sum+=query(1,dfs[top[x]],dfs[x]).sum;
x=fa[top[x]];
}
if(h[x]>h[y])swap(x,y);
t1.maxn=max(t1.maxn,query(1,dfs[x],dfs[y]).maxn);
t1.sum+=query(1,dfs[x],dfs[y]).sum;
return t1;
}
主席树(空间一般<<5)
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
struct node{
int l,r,sum;
}tree[N<<5];
struct none{
int a,b;
}e[N];
bool cmp(none t1,none t2){
return t1.a<t2.a;
}
bool cmp2(none t1,none t2){
return t1.b<t2.b;
}
int n,m,tot,root[N],cnt,add[N];
int read(){
int x=0,f=1;char c=getchar();
while(c>'9' || c<'0'){
if(c=='-')f=-1;
c=getchar();
}
while(c>='0' && c<='9'){
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
int updata(int pre,int l,int r,int x){
int rt=++cnt;
tree[rt].sum=tree[pre].sum+1;
tree[rt].l=tree[pre].l;
tree[rt].r=tree[pre].r;
int mid=(l+r)>>1;
if(l<r){
if(x<=mid)tree[rt].l=updata(tree[pre].l,l,mid,x);
else tree[rt].r=updata(tree[pre].r,mid+1,r,x);
}
return rt;
}
int query(int u,int v,int l,int r,int k){
if(l==r)return l;
int mid=(l+r)>>1;
int del=tree[tree[v].l].sum-tree[tree[u].l].sum;
if(del>=k)
return query(tree[u].l,tree[v].l,l,mid,k);
else return query(tree[u].r,tree[v].r,mid+1,r,k-del);
}
int main(){
n=read(),m=read();
for(int i=1;i<=n;i++)
e[i].a=read(),e[i].b=i;
sort(e+1,e+n+1,cmp);
int rcd=0;
for(int i=1;i<=n;i++){
if(i==1 || e[i].a!=rcd)tot++;
rcd=e[i].a;
add[tot]=e[i].a;
e[i].a=tot;
}
sort(e+1,e+n+1,cmp2);
for(int i=1;i<=n;i++){
root[i]=updata(root[i-1],1,tot,e[i].a);
}
for(int i=1;i<=m;i++){
int l=read(),r=read(),k=read();
int ans=query(root[l-1],root[r],1,tot,k);
printf("%d\n",add[ans]);
}
return 0;
}
带修主席树(树状数组+主席树)
主席树:第i棵线段树是第i-1棵线段树加上一个新节点形成的
相当于是一种前缀和所以查询O(1)修改O(n)
带修主席树:利用树状数组的特性来建树，如第4棵树是第2棵树+第3棵树...
查询O(log n)修改O(log n)
总复杂度:O(\(n log ^2n\))
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+514;
int read(){
int x=0,f=1;char c=getchar();
while(c>'9' || c<'0'){
if(c=='-')f=-1;
c=getchar();
}
while(c>='0' && c<='9'){
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
int cnt,n,m,tot,len,Real[N*2],root[N],rcd_u[N],rcd_v[N],len_u,len_v;
struct st_lsh{
int num,x,flag;
}a[N*2];
struct st_ask{
int opt,l,r,k;
}q[N];
struct st_tree{
int lson,rson,sum;
}e[N*400];
bool cmp1(st_lsh t1,st_lsh t2){
return t1.num<t2.num;
}
bool cmp2(st_lsh t1,st_lsh t2){
if(t1.flag!=t2.flag)return t1.flag<t2.flag;
return t1.x<t2.x;
}
int lowbit(int u){
return u&(-u);
}
void lsh(){
int last=-1;
sort(a+1,a+len+1,cmp1);
for(int i=1;i<=len;i++){
if(a[i].num!=last)tot++;
last=a[i].num;
Real[tot]=a[i].num;
a[i].num=tot;
}
sort(a+1,a+len+1,cmp2);
for(int i=n+1;i<=len;i++)
q[a[i].x].r=a[i].num;
return;
}
void pushup(int u){
e[u].sum=e[e[u].lson].sum+e[e[u].rson].sum;
return;
}
void update(int &u,int l,int r,int val,int add){
if(!u)u=++cnt;
if(l==r){
e[u].sum+=add;
return;
}
int mid=(l+r)>>1;
if(val<=mid)update(e[u].lson,l,mid,val,add);
else update(e[u].rson,mid+1,r,val,add);
pushup(u);
return;
}
void prepare_update(int now,int val,int add){
for(int i=now;i<=n;i+=lowbit(i))
update(root[i],1,tot,val,add);
return;
}
int query(int l,int r,int k){
// cout<<l<<" "<<r<<" "<<k<<" ";
if(l==r)return l;
int mid=(l+r)>>1;
//cout<<mid<<endl;
int del=0;
for(int i=1;i<=len_u;i++)del+=e[e[rcd_u[i]].lson].sum;
for(int i=1;i<=len_v;i++)del-=e[e[rcd_v[i]].lson].sum;
if(del>=k){
for(int i=1;i<=len_u;i++)rcd_u[i]=e[rcd_u[i]].lson;
for(int i=1;i<=len_v;i++)rcd_v[i]=e[rcd_v[i]].lson;
return query(l,mid,k);
}
else{
for(int i=1;i<=len_u;i++)rcd_u[i]=e[rcd_u[i]].rson;
for(int i=1;i<=len_v;i++)rcd_v[i]=e[rcd_v[i]].rson;
return query(mid+1,r,k-del);
}
}
int prepare_query(int v,int u,int k){
len_u=len_v=0;
for(int i=u;i;i-=lowbit(i))rcd_u[++len_u]=root[i];
for(int i=v;i;i-=lowbit(i))rcd_v[++len_v]=root[i];
return query(1,tot,k);
}
/*void sc(int now){
cout<<now<<" "<<e[now].lson<<" "<<e[now].rson<<" "<<e[now].sum<<endl;
if(e[now].lson)sc(e[now].lson);
if(e[now].rson)sc(e[now].rson);
return;
}*/
int main(){
n=read(),m=read();
for(int i=1;i<=n;i++)
a[++len].num=read(),a[len].x=i,a[len].flag=1;
for(int i=1;i<=m;i++){
char tmp;
cin>>tmp;
if(tmp=='Q'){
q[i].opt=1;
q[i].l=read(),q[i].r=read(),q[i].k=read();
}
else {
q[i].opt=2;
q[i].l=read(),q[i].r=read();
a[++len].flag=2,a[len].num=q[i].r,a[len].x=i;
}
}
lsh();
for(int i=1;i<=n;i++)prepare_update(i,a[i].num,1);
for(int i=1;i<=m;i++){
if(q[i].opt==1){
printf("%d\n",Real[prepare_query(q[i].l-1,q[i].r,q[i].k)]);
}
else{
prepare_update(q[i].l,a[q[i].l].num,-1);
prepare_update(q[i].l,q[i].r,1);
a[q[i].l].num=q[i].r;
}
}
return 0;
}
李超线段树
int n,f[N],sum[N],h[N];
struct TREE{
int ht,l,r;
}e[N<<2];
int cnt,xk[N],xb[N];
int calc(int id,int x){return xk[id]*x+xb[id];}
void build(int u,int l,int r){
e[u].l=l,e[u].r=r;if(l==r)return;
int mid=l+r>>1;build(u<<1,l,mid);build(u<<1|1,mid+1,r);
return;
}
void update(int u,int id){
if(calc(id,e[u].l)<calc(e[u].ht,e[u].l) && calc(id,e[u].r)<calc(e[u].ht,e[u].r)){
e[u].ht=id;return;
}
if(calc(id,e[u].l)>=calc(e[u].ht,e[u].l) && calc(id,e[u].r)>=calc(e[u].ht,e[u].r))return;
int mid=e[u].l+e[u].r>>1;
if(xk[e[u].ht]>xk[id])
if(calc(id,mid)<calc(e[u].ht,mid))update(u<<1,e[u].ht),e[u].ht=id;
else update(u<<1|1,id);
else
if(calc(id,mid)<calc(e[u].ht,mid))update(u<<1|1,e[u].ht),e[u].ht=id;
else update(u<<1,id);
return;
}
int query(int u,int x){
if(e[u].l==e[u].r)return calc(e[u].ht,x);
int mid=e[u].l+e[u].r>>1;
if(x<=mid)return min(calc(e[u].ht,x),query(u<<1,x));
else return min(calc(e[u].ht,x),query(u<<1|1,x));
}
void add(int k,int b){
xk[++cnt]=k,xb[cnt]=b;
update(1,cnt);
return;
}