保定网站建设方案,广告设计公司相城黄埭,天津电商网站建设,建筑设计公司属于什么行业[pixiv] https://www.pixiv.net/member_illust.php?modemediumillust_id34352147 暑假的作业#xff0c;颓颓的我总算是写完了 线段树 线段树是一个高级玩意#xff0c;不仅可以求区间和#xff0c;区间最大等等的简单问题#xff0c;灵活运用还有好多变种。自从学… [pixiv] https://www.pixiv.net/member_illust.php?modemediumillust_id34352147 暑假的作业颓颓的我总算是写完了 线段树 线段树是一个高级玩意不仅可以求区间和区间最大等等的简单问题灵活运用还有好多变种。自从学了主席树知道了null自环这种东西后用在线段树上也是得心应手 c3 给一个长为N的数列有M次操作每次操作是以下两种之一 1修改数列中的一个数 2求数列中某连续一段的和 赤裸裸的线段树 c4 给一个长为N的数列有M次操作每次操作时以下三种之一 1修改数列中的一个数 2求数列中某连续一段所有数的两两乘积的和 mod 1000000007 3求数列中某连续一段所有相邻两数乘积的和 mod 1000000007 数据剧毒无比有负数取模就出问题了。对于区间维护答案主要就是如何合并区间。操作3好合并只要记录每个区间的头、尾的数把左右儿子区间的和加起来再加上中间两个数的乘积。关键是操作2要是没有见识过这个脑筋急转弯我可能一辈子都不会 给出N个数 每次可以合并两个数 合并的代价是两个数的乘积 合并得到的数是两个数的和。 问最后把所有数合并成一个数的最小代价。 求这个最小代价对10^97取模的结果。 N 5000000。 题解是 显然无论怎么合并答案都是一样的 任意两个数的乘积恰好会对答案贡献一次。 直接搞就好了 于是这道题的操作2就迎刃而解了 由于这道题坑很多我就不放我wa掉的代码了 大神的AC代码 #includeiostream
#includecstdio
#includealgorithm
using namespace std;
const int maxn100005;
const int mod1000000007;
struct Node{int s1,s2,s3;
}node[maxn2];
int a[maxn];
int n,m;
int slow_mult(int a,int p){if(a0)a(a(mod1))%mod;if(p0)p (p(mod1))%mod;if(ap)swap(a,p);if(p0)return 0;if(p1)return a%mod;int tmpslow_mult(a,p1);if(p1)return ((tmp1)%moda%mod)%mod;else return (tmp1)%mod;
}
inline void update(int root,int l,int r){node[root].s1(node[root1].s1node[root1|1].s1)%mod;node[root].s2(node[root1].s2node[root1|1].s2)%mod;int m(lr)1;node[root].s3((node[root1].s3node[root1|1].s3)%modslow_mult(a[m],a[m1]))%mod;
}
void build(int root,int l,int r){if(lr){node[root].s1a[l];node[root].s2slow_mult(a[l],a[r]);node[root].s30;return ;}int m(lr)1;build(root1,l,m),build(root1|1,m1,r);update(root,l,r);
}
void modify(int root,int l,int r,int x,int val){if(lr){node[root].s1val;node[root].s2slow_mult(val , val);node[root].s30;a[x]val;return;}int m(lr)1;if(xm)modify(root1,l,m,x,val);else modify(root1|1,m1,r,x,val);update(root,l,r);
}
int query1(int root,int l,int r,int x,int y){if(xlry)return node[root].s1;int m(lr)1,ret0;if(xmly)retquery1(root1,l,m,x,y);if(ym1rx)retquery1(root1|1,m1,r,x,y);return ret % mod;
}
int query2(int root,int l,int r,int x,int y){if(xlry)return node[root].s2;int m(lr)1,ret0;if(xmly)retquery2(root1,l,m,x,y);if(ym1rx)retquery2(root1|1,m1,r,x,y);return ret % mod;
}
int query3(int root,int l,int r,int x,int y){if(xlry)return node[root].s3;int m(lr)1,ret0,flag1;if(xmly)retquery3(root1,l,m,x,y),flag*-1;if(ym1rx)retquery3(root1|1,m1,r,x,y),flag*-1;if(flag^1)return ret%mod;else return(ret%modslow_mult(a[m],a[m1]))%mod;
}
void read(int res){int flag1;static char ch;while((chgetchar())0||ch9)if(ch-)flag-1;resch-48;while((chgetchar())0ch9)resres*10ch-48;res*flag;
}
void reads(char res){static char ch;while((chgetchar())!Qch!Mch!A);resch;
}
int main(){read(n),read(m);for(int i1;in;i)read(a[i]),a[i]%mod;build(1,1,n);for(int i1;im;i){char cmd;int x,y;reads(cmd);read(x),read(y);if(cmdM)modify(1,1,n,x,y%mod);else if(cmdQ){int t1query1(1,1,n,x,y);int t2query2(1,1,n,x,y);t1slow_mult(t1,t1);int tmpt1-t2;if(tmp0||tmp1)tmpmod;if(tmp1)tmpmod;printf(%d\n,(tmp1)%mod);}else printf(%d\n,query3(1,1,n,x,y));}return 0;
} c5 给一个长为N的数列有M次操作每次操作是以下两种之一 1将某连续一段同时改成一个数 2求数列中某连续一段的和 也是很基本的线段树 c6 给一个长为N的数列有M次操作每次操作是以下两种之一 1修改数列中的一个数 2求数列中有多少个数比它前面的数都大 其实是裸的楼房重建线段树代码见这里 然后听说这道题用分块也能过为了练习练习这次就用分块了 #includecstdio
#includecstring
#includealgorithm
#includecmath
#includevector
using namespace std;const int N1000005;
const int B400;
const int oo0x7fffffff;int n,m,hh[N];
vectorint a[B];
int blk,pos[N];void getsort(int x){int maxx-oo;a[x].clear();for(int i(x-1)*blk1;imin(n,x*blk);i){if(hh[i]maxx){a[x].push_back(i);maxxhh[i];} }
}
void init(){for(int i1;ipos[n];i){getsort(i);}
}
int erfen(int maxx,int x){int le1,ria[x].size();while(leri){int mid(leri)1;if(hh[a[x][mid-1]]maxx) lemid1;else rimid; }if(hh[a[x][le-1]]maxx){return 0;} return a[x].size()-le1;
}
int query(){int ans0,maxx-oo;for(int i1;ipos[n];i){anserfen(maxx,i);maxxmax(maxx,hh[a[i][a[i].size()-1]]);}return ans;
}
int main(){scanf(%d%d,n,m);blk(int)sqrt((double)n);for(int i1;in;i){scanf(%d,hh[i]);pos[i](i-1)/blk1;} 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\n,query());}}return 0;
} c7 给一个长为N的数列有M次操作每次操作是以下两种之一 1修改数列中的一个数 2求数列中某个值出现了多少次 在做c8之前是没有想到用值域线段树的以为会爆空间int级别的就偷了个懒用map 如何处理值域线段树的空间问题见c8 #includecstdio
#includecstring
#includemap
#includealgorithm
using namespace std;const int N1000005;mapint,int mp;
int a[N];int main(){int n,m;scanf(%d%d,n,m);for(int i1;in;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\n,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掉了全部都加上正无穷就好了。之后又没开longlongint加爆了。。。orz #includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;const ll oo2147483646;
const ll N1000005;ll n,m;
struct Node{Node *ls,*rs;ll ans,maxn,minn,cnt;
}*root,*null,pool[N*80],*tailpool;Node *newnode(){Node *rttail;rt-lsrt-rsnull;rt-ansoo;rt-maxnrt-minnrt-cnt0;return rt;
}
void update(Node *nd){nd-cntnd-ls-cntnd-rs-cnt;nd-ansoo;if(nd-ls-cnt1) nd-ansmin(nd-ans,nd-ls-ans);if(nd-rs-cnt1) nd-ansmin(nd-ans,nd-rs-ans);if(nd-ls-cntnd-rs-cnt) nd-ansmin(nd-ans,nd-rs-minn - nd-ls-maxn);if(nd-rs-cnt) nd-maxnnd-rs-maxn;else nd-maxnnd-ls-maxn;if(nd-ls-cnt) nd-minnnd-ls-minn;else nd-minnnd-rs-minn;
}
void insert(Node *nd,ll le,ll ri,ll pos){if(ndnull) ndnewnode();if(leri){nd-cnt1;nd-ansoo;nd-maxnnd-minnpos;return;}ll mid(leri)/2;if(posmid) insert(nd-ls,le,mid,pos);else insert(nd-rs,mid1,ri,pos);update(nd);
}
void del(Node *nd,ll le,ll ri,ll pos){if(ndnull) return ;if(leri){nd-cnt0;nd-ansnd-maxnnd-minn0;return ;}ll mid(leri)/2;if(posmid) del(nd-ls,le,mid,pos);else del(nd-rs,mid1,ri,pos);update(nd);
}
int main(){nulltail;null-lsnull-rsnull;null-ansnull-minnnull-maxnnull-cnt0;rootnull;scanf(%lld%lld,n,m);ll a;for(ll i1;in;i){scanf(%lld,a);insert(root,0,oooo,aoo);}while(m--){char opt[2];ll x;scanf(%s,opt);if(opt[0]I){scanf(%lld,x);insert(root,0,oooo,xoo);}else if(opt[0]D){scanf(%lld,x);del(root,0,oooo,xoo);}else {if(root-cnt1) printf(%lld\n,root-ans);else printf(-1\n);}}
} c10 给一个长为N的数列有M次操作每次操作是以下两种之一 1修改数列中的一个数 2求数列中第K小的值 第k大问题想来都是线段树。由于每次要修改数据离散化不太可能那么就用上文提到的null来节省空间哎呀我真是太机智了自己yy出来的诶也算是进步吧 #includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;const ll N1000005;
const ll oo2147483646;struct Node {Node *ls,*rs;ll cnt;
}*root,*null,pool[N*80],*tailpool;
ll n,m,a[N];Node *newnode(){Node *rttail;rt-lsrt-rsnull;rt-cnt0;return rt;
}
void modify(Node *nd,ll le,ll ri,ll pos,ll val){if(ndnull) ndnewnode();if(leri){nd-cntval;return ;}ll mid(leri)1;if(posmid) modify(nd-ls,le,mid,pos,val);else modify(nd-rs,mid1,ri,pos,val);nd-cntnd-ls-cntnd-rs-cnt;
}
ll query(Node *nd,ll le,ll ri,ll pos){if(leri)return le;ll mid(leri)1;if(posnd-ls-cnt) return query(nd-ls,le,mid,pos);else return query(nd-rs,mid1,ri,pos-nd-ls-cnt);
}
int main(){nulltail;null-lsnull-rsnull;null-cnt0;rootnull;scanf(%lld%lld,n,m);for(ll i1;in;i){scanf(%lld,a[i]);modify(root,0,oooo,a[i]oo,1);}while(m--){char opt[2];scanf(%s,opt);if(opt[0]Q){ll x;scanf(%lld,x);printf(%lld\n,query(root,0,oooo,x)-oo);}else {ll x,y;scanf(%lld%lld,x,y);modify(root,0,oooo,a[x]oo,-1);modify(root,0,oooo,yoo,1);a[x]y;}}return 0;
} 总结 线段树可腻害可腻害了其实很多的区间问题都可以解决唯一的关键点就是如何快速的区间合并。俗话说“以不变应万变”只要解决区间合并的方法就可以了。 主席树 c2 给一个空数列有M次操作每次操作是以下三种之一 1在数列后加一个数 2求数列中某位置的值 3撤销掉最后进行的若干次操作1和3 感觉像是数组又感觉像是主席树。但是数组又不易用指针写于是一气之下杀鸡用牛刀用线段树来解决数列问题。。。1A #includecstdio
#includecstring
#includealgorithm
using namespace std;const int N1000005;struct Node{Node *ls,*rs;int val;
}*root[N],*null,pool[N*50],*tailpool;
int len[N],m;Node *newnode(){Node *rttail;rt-lsrt-rsnull;rt-val0;return rt;
}
void insert(Node *np,Node *nd,int le,int ri,int pos,int val){ndnewnode();nd-lsnp-ls,nd-rsnp-rs;nd-valnp-val;if(leri){nd-valval;return ;}int mid(leri)1;if(posmid) insert(np-ls,nd-ls,le,mid,pos,val);else insert(nd-rs,nd-rs,mid1,ri,pos,val);
}
int query(Node *nd,int le,int ri,int pos){if(leri) return nd-val;int mid(leri)1;if(posmid) return query(nd-ls,le,mid,pos);else return query(nd-rs,mid1,ri,pos);
}
int main(){nulltail;null-lsnull-rsnull;null-val0;root[0]null;scanf(%d,m);int cnt0;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\n,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求某次操作后连续一段的和 裸主席树就当练手速吧 #includecstdio
#includecstring
#includealgorithm
using namespace std;const int N1000005;struct Node{Node *ls,*rs;int sum;
}*root[N],*null,pool[N*80],*tailpool;
int n,m,a[N];Node *newnode(){Node *rttail;rt-lsrt-rsnull;rt-sum0;return rt;
}
void build(Node *nd,int le,int ri){ndnewnode();if(leri){nd-suma[le];return ;}int mid(leri)1;build(nd-ls,le,mid);build(nd-rs,mid1,ri);nd-sumnd-ls-sumnd-rs-sum;
}
void insert(Node *ne,Node *nd,int le,int ri,int pos,int val){ndnewnode();nd-lsne-ls,nd-rsne-rs;if(leri){nd-sumval;return ;}int mid(leri)1;if(posmid) insert(ne-ls,nd-ls,le,mid,pos,val);else insert(ne-rs,nd-rs,mid1,ri,pos,val);nd-sumnd-ls-sumnd-rs-sum;
}
int query(Node *nd,int le,int ri,int L,int R){if(LleriR) return nd-sum;int mid(leri)1,rt0;if(Lmid) rtquery(nd-ls,le,mid,L,R);if(midR) rtquery(nd-rs,mid1,ri,L,R);return rt;
}
int main(){nulltail;null-lsnull-rsnull;null-sum0;scanf(%d%d,n,m);for(int i1;in;i) scanf(%d,a[i]);build(root[0],1,n);for(int i1;im;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\n,query(root[z],1,n,x,y));root[i]root[i-1];}}return 0;
} c12 给一个长为N的数列有M次操作操作仅有一种 求数列中某连续一段中第K小的值 还是裸的主席树没错我是来挂代码的 #includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;const ll N1000005;
const ll oo2147483646;struct Node {Node *ls,*rs;ll cnt;
}*root[N],*null,pool[N*100],*tailpool;
ll n,m,a[N];Node *newnode(){Node *rttail;rt-lsrt-rsnull;rt-cnt0;return rt;
}
void insert(Node *ne,Node *nd,ll le,ll ri,ll pos){ndnewnode();nd-lsne-ls,nd-rsne-rs;nd-cntne-cnt1;if(leri) return;ll mid(leri)1;if(posmid) insert(ne-ls,nd-ls,le,mid,pos);else insert(ne-rs,nd-rs,mid1,ri,pos);
}
ll query(Node *ne,Node *nd,ll le,ll ri,ll k){if(leri) return le;ll mid(leri)1;ll lscnd-ls-cnt - ne-ls-cnt;if(klsc) return query(ne-ls,nd-ls,le,mid,k);else return query(ne-rs,nd-rs,mid1,ri,k-lsc);
}
int main(){nulltail;null-lsnull-rsnull;null-cnt0;root[0]null;scanf(%lld%lld,n,m);for(ll i1;in;i){scanf(%lld,a[i]);insert(root[i-1],root[i],0,oooo,a[i]oo);}while(m--){ll x,y,z;scanf(%lld%lld%lld,x,y,z);printf(%lld\n,query(root[x-1],root[y],0,oooo,z)-oo);}return 0;
} 数组 c0c1 太简单啦寒假做的 平衡树 c9 给一个长为N的数列有M次操作每次操作是以下两种之一 1删除某个位置的数 2求数列某位置的值 一来就想到treap但是感觉大材小用了就偷了个懒 #includecstdio
#includecstring
#includealgorithm
#includevector
using namespace std;vectorint vec;
int n,m;int main(){scanf(%d%d,n,m);for(int i1;in;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\n,vec[x]);}return 0;
} 好啦就是这样 转载于:https://www.cnblogs.com/LinnBlanc/p/7763147.html
