[pixiv] https://www.pixiv.net/member_illust.php?mode=medium&illust_id=34352147
暑假的作业，颓颓的我总算是写完了
线段树
线段树是一个高级玩意，不仅可以求区间和，区间最大等等的简单问题，灵活运用还有好多变种。自从学了主席树，知道了null自环这种东西后，用在线段树上也是得心应手
c3
给一个长为N的数列，有M次操作，每次操作是以下两种之一：
（1）修改数列中的一个数
（2）求数列中某连续一段的和
赤裸裸的线段树
c4
给一个长为N的数列，有M次操作，每次操作时以下三种之一：
（1）修改数列中的一个数
（2）求数列中某连续一段所有数的两两乘积的和 mod 1000000007
（3）求数列中某连续一段所有相邻两数乘积的和 mod 1000000007
数据剧毒无比，有负数，取模就出问题了。对于区间维护答案，主要就是如何合并区间。操作3好合并，只要记录每个区间的头、尾的数，把左右儿子区间的和加起来，再加上中间两个数的乘积。关键是操作2，要是没有见识过这个脑筋急转弯，我可能一辈子都不会：
给出N个数， 每次可以合并两个数， 合并的代价是两个数的乘积， 合并得到的数是两个数的和。
问最后把所有数合并成一个数的最小代价。 求这个最小代价对10^9+7取模的结果。
N <= 5000000。
题解是：
显然无论怎么合并答案都是一样的， 任意两个数的乘积恰好会对答案贡献一次。
直接搞就好了
于是这道题的操作2就迎刃而解了
由于这道题坑很多，我就不放我wa掉的代码了
大神的AC代码
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=100005;
const int mod=1000000007;
struct Node{
int s1,s2,s3;
}node[maxn<<2];
int a[maxn];
int n,m;
int slow_mult(int a,int p){
if(a<0)a=(a+(mod<<1))%mod;
if(p<0)p =(p+(mod<<1))%mod;
if(a<p)swap(a,p);
if(p==0)return 0;
if(p==1)return a%mod;
int tmp=slow_mult(a,p>>1);
if(p&1)return ((tmp<<1)%mod+a%mod)%mod;
else return (tmp<<1)%mod;
}
inline void update(int root,int l,int r){
node[root].s1=(node[root<<1].s1+node[root<<1|1].s1)%mod;
node[root].s2=(node[root<<1].s2+node[root<<1|1].s2)%mod;
int m=(l+r)>>1;
node[root].s3=((node[root<<1].s3+node[root<<1|1].s3)%mod+slow_mult(a[m],a[m+1]))%mod;
}
void build(int root,int l,int r){
if(l==r){
node[root].s1=a[l];
node[root].s2=slow_mult(a[l],a[r]);
node[root].s3=0;
return ;
}
int m=(l+r)>>1;
build(root<<1,l,m),build(root<<1|1,m+1,r);
update(root,l,r);
}
void modify(int root,int l,int r,int x,int val){
if(l==r){
node[root].s1=val;
node[root].s2=slow_mult(val , val);
node[root].s3=0;
a[x]=val;
return;
}
int m=(l+r)>>1;
if(x<=m)modify(root<<1,l,m,x,val);
else modify(root<<1|1,m+1,r,x,val);
update(root,l,r);
}
int query1(int root,int l,int r,int x,int y){
if(x<=l&&r<=y)return node[root].s1;
int m=(l+r)>>1,ret=0;
if(x<=m&&l<=y)ret+=query1(root<<1,l,m,x,y);
if(y>=m+1&&r>=x)ret+=query1(root<<1|1,m+1,r,x,y);
return ret % mod;
}
int query2(int root,int l,int r,int x,int y){
if(x<=l&&r<=y)return node[root].s2;
int m=(l+r)>>1,ret=0;
if(x<=m&&l<=y)ret+=query2(root<<1,l,m,x,y);
if(y>=m+1&&r>=x)ret+=query2(root<<1|1,m+1,r,x,y);
return ret % mod;
}
int query3(int root,int l,int r,int x,int y){
if(x<=l&&r<=y)return node[root].s3;
int m=(l+r)>>1,ret=0,flag=1;
if(x<=m&&l<=y)ret+=query3(root<<1,l,m,x,y),flag*=-1;
if(y>=m+1&&r>=x)ret+=query3(root<<1|1,m+1,r,x,y),flag*=-1;
if(flag^1)return ret%mod;
else return(ret%mod+slow_mult(a[m],a[m+1]))%mod;
}
void read(int &res){
int flag=1;static char ch;
while((ch=getchar())<'0'||ch>'9')if(ch=='-')flag=-1;res=ch-48;
while((ch=getchar())>='0'&&ch<='9')res=res*10+ch-48;res*=flag;
}
void reads(char &res){
static char ch;
while((ch=getchar())!='Q'&&ch!='M'&&ch!='A');res=ch;
}
int main(){
read(n),read(m);
for(int i=1;i<=n;i++)read(a[i]),a[i]%=mod;
build(1,1,n);
for(int i=1;i<=m;i++){
char cmd;
int x,y;
reads(cmd);read(x),read(y);
if(cmd=='M')modify(1,1,n,x,y%mod);
else if(cmd=='Q'){
int t1=query1(1,1,n,x,y);
int t2=query2(1,1,n,x,y);
t1=slow_mult(t1,t1);
int tmp=t1-t2;
if(tmp<0||tmp&1)tmp+=mod;
if(tmp&1)tmp+=mod;
printf("%d
",(tmp>>1)%mod);
}else printf("%d
",query3(1,1,n,x,y));
}
return 0;
}c5
给一个长为N的数列，有M次操作，每次操作是以下两种之一：
（1）将某连续一段同时改成一个数
（2）求数列中某连续一段的和
也是很基本的线段树
c6
给一个长为N的数列，有M次操作，每次操作是以下两种之一：
（1）修改数列中的一个数
（2）求数列中有多少个数比它前面的数都大
其实是裸的楼房重建，线段树代码见这里
然后听说这道题用分块也能过，为了练习练习，这次就用分块了
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
const int N=100000+5;
const int B=400;
const int oo=0x7fffffff;
int n,m,hh[N];
vector<int> a[B];
int blk,pos[N];
void getsort(int x){
int maxx=-oo;
a[x].clear();
for(int i=(x-1)*blk+1;i<=min(n,x*blk);i++){
if(hh[i]>maxx){
a[x].push_back(i);
maxx=hh[i];
}
}
}
void init(){
for(int i=1;i<=pos[n];i++){
getsort(i);
}
}
int erfen(int maxx,int x){
int le=1,ri=a[x].size();
while(le<ri){
int mid=(le+ri)>>1;
if(hh[a[x][mid-1]]<=maxx) le=mid+1;
else ri=mid;
}
if(hh[a[x][le-1]]<=maxx){
return 0;
}
return a[x].size()-le+1;
}
int query(){
int ans=0,maxx=-oo;
for(int i=1;i<=pos[n];i++){
ans+=erfen(maxx,i);
maxx=max(maxx,hh[a[i][a[i].size()-1]]);
}
return ans;
}
int main(){
scanf("%d%d",&n,&m);
blk=(int)sqrt((double)n);
for(int i=1;i<=n;i++){
scanf("%d",&hh[i]);
pos[i]=(i-1)/blk+1;
}
init();
while(m--){
char opt[2];
scanf("%s",opt);
if(opt[0]=='M'){
int x,y;
scanf("%d%d",&x,&y);
hh[x]=y;
getsort(pos[x]);
}
else{
printf("%d
",query());
}
}
return 0;
}c7
给一个长为N的数列，有M次操作，每次操作是以下两种之一：
（1）修改数列中的一个数
（2）求数列中某个值出现了多少次
在做c8之前是没有想到用值域线段树的，以为会爆空间（int级别的），就偷了个懒，用map
如何处理值域线段树的空间问题，见c8
#include<cstdio>
#include<cstring>
#include<map>
#include<algorithm>
using namespace std;
const int N=100000+5;
map<int,int> mp;
int a[N];
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
mp[a[i]]++;
}
while(m--){
char opt[2];
scanf("%s",opt);
if(opt[0]=='M'){
int x,y;
scanf("%d%d",&x,&y);
mp[a[x]]--;
mp[y]++;
a[x]=y;
}
else{
int x;
scanf("%d",&x);
printf("%d
",mp[x]);
}
}
return 0;
}c8
给一个长为N的数列，有M次操作，每次操作是以下三种之一：
（1）插入一个数，若已存在则忽略
（2）删除一个数，若不存在则忽略
（3）求数列中任意两数之差绝对值的最小值
先不考虑空间问题，我一来就想到值域线段树。计算存在的数与最近的前后两数的差值的最小值。每个区间储存存在的最小数和最大数。合并时，左区间的ans，右区间的ans，左区间最大数和右区间的最小数的差，取min。
那么怎么处理空间大小问题呢？数据是2^31，但N,M的范围是10^5，也就是说最少都有2^31-10^5的数根本和此题无关，是浪费空间。其维护的值都是一样的，那么为什么不指向同一个空间呢？于是就把主席树里的null搬过来，不存在的值就由null代替
然后我猜数据里有负数，结果在划分区间是没注意向上还是向下取整的问题，结果T掉了，全部都加上正无穷就好了。之后又没开longlong，int加爆了。。。orz
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const ll oo=2147483646;
const ll N=100000+5;
ll n,m;
struct Node{
Node *ls,*rs;
ll ans,maxn,minn,cnt;
}*root,*null,pool[N*80],*tail=pool;
Node *newnode(){
Node *rt=++tail;
rt->ls=rt->rs=null;
rt->ans=oo;
rt->maxn=rt->minn=rt->cnt=0;
return rt;
}
void update(Node *nd){
nd->cnt=nd->ls->cnt+nd->rs->cnt;
nd->ans=oo;
if(nd->ls->cnt>1) nd->ans=min(nd->ans,nd->ls->ans);
if(nd->rs->cnt>1) nd->ans=min(nd->ans,nd->rs->ans);
if(nd->ls->cnt&&nd->rs->cnt) nd->ans=min(nd->ans,nd->rs->minn - nd->ls->maxn);
if(nd->rs->cnt) nd->maxn=nd->rs->maxn;
else nd->maxn=nd->ls->maxn;
if(nd->ls->cnt) nd->minn=nd->ls->minn;
else nd->minn=nd->rs->minn;
}
void insert(Node *&nd,ll le,ll ri,ll pos){
if(nd==null) nd=newnode();
if(le==ri){
nd->cnt=1;
nd->ans=oo;
nd->maxn=nd->minn=pos;
return;
}
ll mid=(le+ri)/2;
if(pos<=mid) insert(nd->ls,le,mid,pos);
else insert(nd->rs,mid+1,ri,pos);
update(nd);
}
void del(Node *&nd,ll le,ll ri,ll pos){
if(nd==null) return ;
if(le==ri){
nd->cnt=0;
nd->ans=nd->maxn=nd->minn=0;
return ;
}
ll mid=(le+ri)/2;
if(pos<=mid) del(nd->ls,le,mid,pos);
else del(nd->rs,mid+1,ri,pos);
update(nd);
}
int main(){
null=++tail;
null->ls=null->rs=null;
null->ans=null->minn=null->maxn=null->cnt=0;
root=null;
scanf("%lld%lld",&n,&m);
ll a;
for(ll i=1;i<=n;i++){
scanf("%lld",&a);
insert(root,0,oo+oo,a+oo);
}
while(m--){
char opt[2];
ll x;
scanf("%s",opt);
if(opt[0]=='I'){
scanf("%lld",&x);
insert(root,0,oo+oo,x+oo);
}
else if(opt[0]=='D'){
scanf("%lld",&x);
del(root,0,oo+oo,x+oo);
}
else {
if(root->cnt>1) printf("%lld
",root->ans);
else printf("-1
");
}
}
}c10
给一个长为N的数列，有M次操作，每次操作是以下两种之一：
（1）修改数列中的一个数
（2）求数列中第K小的值
第k大问题，想来都是线段树。由于每次要修改数据，离散化不太可能，那么就用上文提到的null来节省空间（哎呀我真是太机智了，自己yy出来的诶，也算是进步吧）
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const ll N=100000+5;
const ll oo=2147483646;
struct Node {
Node *ls,*rs;
ll cnt;
}*root,*null,pool[N*80],*tail=pool;
ll n,m,a[N];
Node *newnode(){
Node *rt=++tail;
rt->ls=rt->rs=null;
rt->cnt=0;
return rt;
}
void modify(Node *&nd,ll le,ll ri,ll pos,ll val){
if(nd==null) nd=newnode();
if(le==ri){
nd->cnt+=val;
return ;
}
ll mid=(le+ri)>>1;
if(pos<=mid) modify(nd->ls,le,mid,pos,val);
else modify(nd->rs,mid+1,ri,pos,val);
nd->cnt=nd->ls->cnt+nd->rs->cnt;
}
ll query(Node *nd,ll le,ll ri,ll pos){
if(le==ri)
return le;
ll mid=(le+ri)>>1;
if(pos<=nd->ls->cnt) return query(nd->ls,le,mid,pos);
else return query(nd->rs,mid+1,ri,pos-nd->ls->cnt);
}
int main(){
null=++tail;
null->ls=null->rs=null;
null->cnt=0;
root=null;
scanf("%lld%lld",&n,&m);
for(ll i=1;i<=n;i++){
scanf("%lld",&a[i]);
modify(root,0,oo+oo,a[i]+oo,1);
}
while(m--){
char opt[2];
scanf("%s",opt);
if(opt[0]=='Q'){
ll x;
scanf("%lld",&x);
printf("%lld
",query(root,0,oo+oo,x)-oo);
}
else {
ll x,y;
scanf("%lld%lld",&x,&y);
modify(root,0,oo+oo,a[x]+oo,-1);
modify(root,0,oo+oo,y+oo,1);
a[x]=y;
}
}
return 0;
}总结：
线段树可腻害可腻害了，其实很多的区间问题都可以解决，唯一的关键点就是如何快速的区间合并。俗话说“以不变应万变”，只要解决区间合并的方法就可以了。
主席树
c2
给一个空数列，有M次操作，每次操作是以下三种之一：
（1）在数列后加一个数
（2）求数列中某位置的值
（3）撤销掉最后进行的若干次操作（1和3）
感觉像是数组，又感觉像是主席树。但是数组又不易用指针写，于是一气之下杀鸡用牛刀，用线段树来解决数列问题。。。1A
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=100000+5;
struct Node{
Node *ls,*rs;
int val;
}*root[N],*null,pool[N*50],*tail=pool;
int len[N],m;
Node *newnode(){
Node *rt=++tail;
rt->ls=rt->rs=null;
rt->val=0;
return rt;
}
void insert(Node *np,Node *&nd,int le,int ri,int pos,int val){
nd=newnode();
nd->ls=np->ls,nd->rs=np->rs;
nd->val=np->val;
if(le==ri){
nd->val=val;
return ;
}
int mid=(le+ri)>>1;
if(pos<=mid) insert(np->ls,nd->ls,le,mid,pos,val);
else insert(nd->rs,nd->rs,mid+1,ri,pos,val);
}
int query(Node *nd,int le,int ri,int pos){
if(le==ri) return nd->val;
int mid=(le+ri)>>1;
if(pos<=mid) return query(nd->ls,le,mid,pos);
else return query(nd->rs,mid+1,ri,pos);
}
int main(){
null=++tail;
null->ls=null->rs=null;
null->val=0;
root[0]=null;
scanf("%d",&m);
int cnt=0;
while(m--){
char opt[2];
int x;
scanf("%s%d",opt,&x);
if(opt[0]=='A'){
cnt++;
len[cnt]=len[cnt-1]+1;
insert(root[cnt-1],root[cnt],1,N,len[cnt],x);
}
else if(opt[0]=='Q'){
printf("%d
",query(root[cnt],1,N,x));
}
else{
cnt++;
root[cnt]=root[cnt-x-1];
len[cnt]=len[cnt-x-1];
}
}
return 0;
}c11
给一个长为N的数列，有M次操作，每次操作是以下两种之一：
（1）修改数列中的一个数
（2）求某次操作后连续一段的和
裸主席树，就当练手速吧
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=100000+5;
struct Node{
Node *ls,*rs;
int sum;
}*root[N],*null,pool[N*80],*tail=pool;
int n,m,a[N];
Node *newnode(){
Node *rt=++tail;
rt->ls=rt->rs=null;
rt->sum=0;
return rt;
}
void build(Node *&nd,int le,int ri){
nd=newnode();
if(le==ri){
nd->sum=a[le];
return ;
}
int mid=(le+ri)>>1;
build(nd->ls,le,mid);
build(nd->rs,mid+1,ri);
nd->sum=nd->ls->sum+nd->rs->sum;
}
void insert(Node *ne,Node *&nd,int le,int ri,int pos,int val){
nd=newnode();
nd->ls=ne->ls,nd->rs=ne->rs;
if(le==ri){
nd->sum=val;
return ;
}
int mid=(le+ri)>>1;
if(pos<=mid) insert(ne->ls,nd->ls,le,mid,pos,val);
else insert(ne->rs,nd->rs,mid+1,ri,pos,val);
nd->sum=nd->ls->sum+nd->rs->sum;
}
int query(Node *nd,int le,int ri,int L,int R){
if(L<=le&&ri<=R) return nd->sum;
int mid=(le+ri)>>1,rt=0;
if(L<=mid) rt+=query(nd->ls,le,mid,L,R);
if(mid<R) rt+=query(nd->rs,mid+1,ri,L,R);
return rt;
}
int main(){
null=++tail;
null->ls=null->rs=null;
null->sum=0;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
build(root[0],1,n);
for(int i=1;i<=m;i++){
char opt[2];
scanf("%s",opt);
if(opt[0]=='M'){
int x,y;
scanf("%d%d",&x,&y);
insert(root[i-1],root[i],1,n,x,y);
}
else{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
printf("%d
",query(root[z],1,n,x,y));
root[i]=root[i-1];
}
}
return 0;
}c12
给一个长为N的数列，有M次操作，操作仅有一种：
求数列中某连续一段中第K小的值
还是裸的主席树，没错我是来挂代码的
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const ll N=100000+5;
const ll oo=2147483646;
struct Node {
Node *ls,*rs;
ll cnt;
}*root[N],*null,pool[N*100],*tail=pool;
ll n,m,a[N];
Node *newnode(){
Node *rt=++tail;
rt->ls=rt->rs=null;
rt->cnt=0;
return rt;
}
void insert(Node *ne,Node *&nd,ll le,ll ri,ll pos){
nd=newnode();
nd->ls=ne->ls,nd->rs=ne->rs;
nd->cnt=ne->cnt+1;
if(le==ri) return;
ll mid=(le+ri)>>1;
if(pos<=mid) insert(ne->ls,nd->ls,le,mid,pos);
else insert(ne->rs,nd->rs,mid+1,ri,pos);
}
ll query(Node *ne,Node *nd,ll le,ll ri,ll k){
if(le==ri) return le;
ll mid=(le+ri)>>1;
ll lsc=nd->ls->cnt - ne->ls->cnt;
if(k<=lsc) return query(ne->ls,nd->ls,le,mid,k);
else return query(ne->rs,nd->rs,mid+1,ri,k-lsc);
}
int main(){
null=++tail;
null->ls=null->rs=null;
null->cnt=0;
root[0]=null;
scanf("%lld%lld",&n,&m);
for(ll i=1;i<=n;i++){
scanf("%lld",&a[i]);
insert(root[i-1],root[i],0,oo+oo,a[i]+oo);
}
while(m--){
ll x,y,z;
scanf("%lld%lld%lld",&x,&y,&z);
printf("%lld
",query(root[x-1],root[y],0,oo+oo,z)-oo);
}
return 0;
}数组
c0，c1
太简单啦，寒假做的
平衡树
c9
给一个长为N的数列，有M次操作，每次操作是以下两种之一：
（1）删除某个位置的数
（2）求数列某位置的值
一来就想到treap，但是感觉大材小用了，就偷了个懒
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
vector<int> vec;
int n,m;
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
int a;
scanf("%d",&a);
vec.push_back(a);
}
while(m--){
char opt[2];
int x;
scanf("%s%d",opt,&x);
x--;
if(opt[0]=='D')
vec.erase(vec.begin()+x);
else printf("%d
",vec[x]);
}
return 0;
}好啦，就是这样