《线段树学习笔记》 AC代码索引
2024-09-08 18:50:54
P3372 【模板】线段树 1 | LibreOJ#132. 树状数组 3 ：区间修改，区间查询
#include <bits/stdc++.h>
#define int long long
using namespace std;
#define ls (i<<1) // 左子节点
#define rs (i<<1|1) // 右子节点
#define mid ((l+r)>>1) // 当前区间中部
int tree[1000005<<2],tag[1000005<<2];
int n,m;
int a[1000005];
void pushup(int i){
tree[i]=tree[ls]+tree[rs];
}
void build(int i,int l,int r){
if(l==r){
tree[i]=a[l];
return ;
}
build(ls,l,mid);
build(rs,mid+1,r);
pushup(i);
}
void pushdown(int i,int l,int r){
if(tag[i]){ // 如果有标记
tag[ls]+=tag[i]; // 左节点更新标记
tag[rs]+=tag[i]; // 右节点更新标记
tree[ls]+=(mid-l+1)*tag[i]; // 左节点更新值
tree[rs]+=(r-mid)*tag[i]; // 右节点更新值
tag[i]=0; // 清除当前节点标记
}
}
void update(int i,int l,int r,int x,int y,int k){
if(l>=x&&r<=y){ // 被包含
tree[i]+=(r-l+1)*k; // 修改本身的值
tag[i]+=k; // 打标记
return ;
}
pushdown(i,l,r); // 标记下传
if(mid>=x) update(ls,l,mid,x,y,k);
if(mid<y) update(rs,mid+1,r,x,y,k); // 二分
pushup(i); // 上传
}
int query(int i,int l,int r,int x,int y){
if(l>=x&&r<=y){ // 被包含
return tree[i];
}
pushdown(i,l,r);// 标记下传
int ret=0;
if(mid>=x) ret+=query(ls,l,mid,x,y);
if(mid<y) ret+=query(rs,mid+1,r,x,y);// 二分
return ret;
}
signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
build(1,1,n);
while(m--){
int opt,l,r,k;
cin>>opt>>l>>r;
if(opt==1){
cin>>k;
update(1,1,n,l,r,k);
}
else{
cout<<query(1,1,n,l,r)<<'\n';
}
}
return 0;
}
P3374 【模板】树状数组 1 | LibreOJ#130. 树状数组 1 ：单点修改，区间查询
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int SIZE = 1e6 + 5;
int t[SIZE << 2], a[SIZE];
int n, m;
void pushup(int i) {
t[i] = t[i << 1] + t[i << 1 | 1];
}
void build(int i, int l, int r) {
if (l == r) {
t[i] = a[l];
return;
}
int mid = (l + r) >> 1;
build(i << 1, l, mid);
build(i << 1 | 1, mid + 1, r);
pushup(i);
}
int query(int ql, int qr, int l, int r, int i) {
if (ql <= l && r <= qr) {
return t[i];
}
int mid = (l + r) >> 1;
int result = 0;
if (ql <= mid) {
result += query(ql, qr, l, mid, i << 1);
}
if (qr > mid) {
result += query(ql, qr, mid + 1, r, i << 1 | 1);
}
return result;
}
void update(int p, int l, int r, int i, int v) {
if (l == r) {
t[i] += v;
return;
}
int mid = (l + r) >> 1;
if (p <= mid) {
update(p, l, mid, i << 1, v);
}
if (p > mid) {
update(p, mid + 1, r, i << 1 | 1, v);
}
pushup(i);
}
signed main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
build(1, 1, n);
while (m--) {
int op, x, y;
cin >> op >> x >> y;
if (op == 1) {
update(x, 1, n, 1, y);
} else {
cout << query(x, y, 1, n, 1) << endl;
}
}
return 0;
}
P1531 I Hate It
#include<bits/stdc++.h>
using namespace std;
const int SIZE = 2e5+5;
int t[SIZE<<2],a[SIZE];
int n,m;
void pushup(int i){
t[i]=max(t[i<<1],t[i<<1|1]);
}
void build(int i,int l,int r){
if(l==r){
t[i]=a[l];
return;
}
int mid=(l+r)>>1;
build(i<<1,l,mid);
build(i<<1|1,mid+1,r);
pushup(i);
}
int query(int ql,int qr,int l,int r,int i){
if(ql<=l && r <= qr){
return t[i];
}
int mid = (l+r)>>1;
int result = 0;
if(ql <= mid){
result = max(result,query(ql,qr,l,mid,i<<1));
}
if(qr > mid){
result = max(result,query(ql,qr,mid+1,r,i<<1|1));
}
return result;
}
void update(int p,int l,int r,int i,int v){
if(l==r){
if(t[i]<v){
t[i]=v;
}
return;
}
int mid=(l+r)>>1;
if(p <= mid){
update(p,l,mid,i<<1,v);
}
if(p > mid){
update(p,mid+1,r,i<<1|1,v);
}
pushup(i);
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
build(1,1,n);
while(m--){
char op;int a,b;
cin>>op>>a>>b;
if(op=='Q'){
cout<<query(a,b,1,n,1)<<endl;
}
else{
update(a,1,n,1,b);
}
}
return 0;
}
P1198 [JSOI2008]最大数 | BZOJ1012 [JSOI2008]最大数maxnumber
#include<bits/stdc++.h>
#define int long long
using namespace std;
int t[800005];
int m,d;
char op;
int x,tt,cnt;
void pushup(int i){
t[i]=max(t[i<<1],t[i<<1|1])%d;
}
void update(int pv,int v,int i,int l,int r){
if(l==r){
t[i]=v;
return;
}
int mid=(l+r)>>1;
if(mid>=pv){
update(pv,v,i<<1,l,mid);
}
if(mid<pv){
update(pv,v,i<<1|1,mid+1,r);
}
pushup(i);
}
int ask(int ql,int qr,int i,int l,int r){
if(ql<=l&&qr>=r){
return t[i];
}
int mid=(l+r)>>1;
int result=LLONG_MIN;
if(ql<=mid){
result=max(result,ask(ql,qr,i<<1,l,mid));
}
if(qr>mid){
result=max(result,ask(ql,qr,i<<1|1,mid+1,r));
}
return result;
}
signed main(){
cin>>m>>d;
for(int i=1;i<=m;i++){
cin>>op>>x;
if(op=='A'){
update(cnt+1,(x+tt)%d,1,1,m);
cnt++;
}
else{
if(x==0)tt=0;
else tt=ask(cnt-x+1,cnt,1,1,m)%d;
cout<<tt<<endl;
}
}
return 0;
}
P2880 [USACO07JAN] Balanced Lineup G
#include <bits/stdc++.h>
using namespace std;
int n, q, a[1000005];
int maxn[1000005 << 2], minn[1000005 << 2];
bool flag = true;
void pushup(int i) {
maxn[i] = max(maxn[i << 1], maxn[i << 1 | 1]);
minn[i] = min(minn[i << 1], minn[i << 1 | 1]);
}
void build(int i, int l, int r) {
if (l == r) {
maxn[i] = minn[i] = a[l];
return;
}
int mid = (l + r) >> 1;
build(i << 1, l, mid);
build(i << 1 | 1, mid + 1, r);
pushup(i);
}
int querymax(int L, int R, int l, int r, int i) {
if (L <= l && r <= R) {
return maxn[i];
}
int mid = (l + r) >> 1;
int result = INT_MIN;
if (L <= mid) {
result = max(result, querymax(L, R, l, mid, i << 1));
}
if (R > mid) {
result = max(result, querymax(L, R, mid + 1, r, i << 1 | 1));
}
return result;
}
int querymin(int L, int R, int l, int r, int i) {
if (L <= l && r <= R) {
return minn[i];
}
int mid = (l + r) >> 1;
int result = INT_MAX;
if (L <= mid) {
result = min(result, querymin(L, R, l, mid, i << 1));
}
if (R > mid) {
result = min(result, querymin(L, R, mid + 1, r, i << 1 | 1));
}
return result;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> q;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
build(1, 1, n);
while(q--){
int l,r;
cin>>l>>r;
cout<<querymax(l,r,1,n,1)-querymin(l,r,1,n,1)<<endl;
}
return 0;
}
P4392 [BOI2007]Sound 静音问题
#include <bits/stdc++.h>
using namespace std;
int n, m, c, a[1000005];
int maxn[1000005 << 2], minn[1000005 << 2];
bool flag = true;
void pushup(int i) {
maxn[i] = max(maxn[i << 1], maxn[i << 1 | 1]);
minn[i] = min(minn[i << 1], minn[i << 1 | 1]);
}
void build(int i, int l, int r) {
if (l == r) {
maxn[i] = minn[i] = a[l];
return;
}
int mid = (l + r) >> 1;
build(i << 1, l, mid);
build(i << 1 | 1, mid + 1, r);
pushup(i);
}
int querymax(int L, int R, int l, int r, int i) {
if (L <= l && r <= R) {
return maxn[i];
}
int mid = (l + r) >> 1;
int result = INT_MIN;
if (L <= mid) {
result = max(result, querymax(L, R, l, mid, i << 1));
}
if (R > mid) {
result = max(result, querymax(L, R, mid + 1, r, i << 1 | 1));
}
return result;
}
int querymin(int L, int R, int l, int r, int i) {
if (L <= l && r <= R) {
return minn[i];
}
int mid = (l + r) >> 1;
int result = INT_MAX;
if (L <= mid) {
result = min(result, querymin(L, R, l, mid, i << 1));
}
if (R > mid) {
result = min(result, querymin(L, R, mid + 1, r, i << 1 | 1));
}
return result;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m >> c;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
build(1, 1, n);
for (int i = 1; i <= n - m + 1; i++) {
//cout<<i<<' '<<querymax(i, i + m - 1, 1, n, 1)<<' '<<querymin(i, i + m - 1, 1, n, 1)<<endl;
if ((querymax(i, i + m - 1, 1, n, 1) - querymin(i, i + m - 1, 1, n, 1)) <= c) {
cout << i << endl;
flag = false;
}
}
if (flag) {
cout << "NONE" << endl;
}
return 0;
}
（原创题）Game 1：人道寄奴曾住
内带数据生成程序
sj。
#include<bits/stdc++.h>
using namespace std;
const int SIZE = 2e5+5;
int t[SIZE<<2],a[SIZE];
int n,m;
void pushup(int i) {
t[i]=max(t[i<<1],t[i<<1|1]);
}
void build(int i,int l,int r) {
if(l==r) {
t[i]=a[l];
return;
}
int mid=(l+r)>>1;
build(i<<1,l,mid);
build(i<<1|1,mid+1,r);
pushup(i);
}
int query(int ql,int qr,int l,int r,int i) {
if(ql<=l && r <= qr) {
return t[i];
}
int mid = (l+r)>>1;
int result = 0;
if(ql <= mid) {
result = max(result,query(ql,qr,l,mid,i<<1));
}
if(qr > mid) {
result = max(result,query(ql,qr,mid+1,r,i<<1|1));
}
return result;
}
void update(int p,int l,int r,int i,int v) {
if(l==r) {
if(t[i]<v) {
t[i]=max(t[i],v);
}
return;
}
int mid=(l+r)>>1;
if(p <= mid) {
update(p,l,mid,i<<1,v);
}
if(p > mid) {
update(p,mid+1,r,i<<1|1,v);
}
pushup(i);
}
void solve() {
memset(a,0,sizeof(a));
memset(t,0,sizeof(t));
cin>>n>>m;
for(int i=1; i<=n; i++) {
cin>>a[i];
}
build(1,1,n);
while(m--) {
int opt,a,b;
cin>>opt>>a>>b;
if(opt==2) {
if(b<a)swap(b,a);
cout<<query(a,b,1,n,1)<<endl;
} else {
update(a,1,n,1,b);
}
}
return;
}
int sj() {
srand(time(0));
for(int i=1; i<=49; i++) {
char buff[114],buff2[514];
sprintf(buff,"data/%d.in",i);
sprintf(buff2,"data/%d.out",i);
freopen(buff,"w",stdout);
int n=rand()%(int(1e5))+1,m=rand()%(int(4000))+1;
cout<<n<<' '<<m<<endl;
for(int j=1; j<=n; j++) {
cout<<rand()%(int(1e5))+1<<' ';
}
cout<<endl;
for(int j=1; j<=m; j++) {
int op = rand()%2+1;
int l,r;
if(op==1) {
l=rand()%(int(n))+1;
r=rand()%(int(1e5))+1;
} else {
l=rand()%(int(n))+1;
r=rand()%(int(n))+1;
}
cout<<op<<' '<<l<<' '<<r<<endl;
}
fclose(stdout);
freopen(buff2,"w",stdout);
freopen(buff,"r",stdin);
solve();
fclose(stdin);
fclose(stdout);
}
return 0;
}
int main(){
solve();
}
P1253 [yLOI2018] 扶苏的问题
#include <bits/stdc++.h>
#define ls (i<<1)
#define rs (i<<1|1)
#define mid ((l+r)>>1)
#define int long long
using namespace std;
struct node{
int maxv,add,cov;
node(){
this->cov = LLONG_MIN;
this->add = 0;
}
} t[4000005];
int a[1000005];
int n,q;
inline void pushup(int i){
t[i].maxv=max(t[ls].maxv,t[rs].maxv);
}
void build(int i,int l,int r){
if(l==r){
t[i].maxv=a[l];
}
else{
build(ls,l,mid);
build(rs,mid+1,r);
pushup(i);
}
}
void pushdown(int i){
if(t[i].cov!=LLONG_MIN){
t[ls].maxv=t[rs].maxv=t[ls].cov=t[rs].cov=t[i].cov;
//t[ls].cov+=t[ls].add;
//t[rs].cov+=t[rs].add;
t[ls].add=t[rs].add=0;
t[i].cov=LLONG_MIN;
}
if(t[i].add){
t[ls].add+=t[i].add;
t[rs].add+=t[i].add;
t[ls].maxv+=t[i].add;
t[rs].maxv+=t[i].add;
t[i].add=0;
}
}
void add(int ql,int qr,int v,int i,int l,int r){
if(ql<=l&&r<=qr){
t[i].maxv+=v;
t[i].add+=v;
return;
}
pushdown(i);
if(ql<=mid){
add(ql,qr,v,ls,l,mid);
}
if(mid<qr){
add(ql,qr,v,rs,mid+1,r);
}
pushup(i);
}
void cover(int ql,int qr,int v,int i,int l,int r){
if(ql<=l&&r<=qr){
t[i].maxv=v;
t[i].cov=v;
t[i].add=0;
return;
}
pushdown(i);
if(ql<=mid){
cover(ql,qr,v,ls,l,mid);
}
if(mid<qr){
cover(ql,qr,v,rs,mid+1,r);
}
pushup(i);
}
int query(int ql,int qr,int i,int l,int r){
if(ql<=l&&r<=qr){
return t[i].maxv;
}
pushdown(i);
int result=LLONG_MIN;
if(ql<=mid){
result=max(result,query(ql,qr,ls,l,mid));
}
if(mid<qr){
result=max(result,query(ql,qr,rs,mid+1,r));
}
return result;
}
signed main(){
cin>>n>>q;
for(int i=1;i<=n;i++){
cin>>a[i];
}
build(1,1,n);
while(q--){
int op,l,r,x;
cin>>op;
if(op==2){
cin>>l>>r>>x;
add(l,r,x,1,1,n);
}
if(op==1){
cin>>l>>r>>x;
cover(l,r,x,1,1,n);
}
if(op==3){
cin>>l>>r;
cout<<query(l,r,1,1,n)<<endl;
}
}
return 0;
}
P2023 [AHOI2009] 维护序列 | LibreOJ#10129. 「一本通 4.3 练习 3」维护序列
#include <bits/stdc++.h>
using namespace std;
long long c[500010];
long long p;
struct sgt{
long long sum[2000010];
long long addv[2000010];
long long mulv[2000010];
void build(int o,int l,int r){
addv[o]=0;
mulv[o]=1;
if(l==r)sum[o]=c[l];
else{
int mid=(l+r)>>1;
int lson=o<<1;
int rson=lson|1;
build(lson,l,mid);
build(rson,mid+1,r);
sum[o]=(sum[lson]+sum[rson])%p;
}
}
void push_down(int o,int l,int r,int mid,int lson,int rson){
mulv[lson]=(mulv[lson]*mulv[o])%p;
mulv[rson]=(mulv[rson]*mulv[o])%p;
addv[lson]=(addv[lson]*mulv[o])%p;
addv[rson]=(addv[rson]*mulv[o])%p;
sum[lson]=(sum[lson]*mulv[o])%p;
sum[rson]=(sum[rson]*mulv[o])%p;
mulv[o]=1;
addv[lson]=(addv[lson]+addv[o])%p;
addv[rson]=(addv[rson]+addv[o])%p;
sum[lson]=(sum[lson]+(mid-l+1)*addv[o])%p;
sum[rson]=(sum[rson]+(r-mid)*addv[o])%p;
addv[o]=0;
}
void addall(int o,int l,int r,int a,int b,int x){
if(l>=a && r<=b){
addv[o]=(addv[o]+x)%p;
sum[o]=(sum[o]+(r-l+1)*x)%p;
return;
}
else{
int mid=(l+r)>>1;
int lson=o<<1;
int rson=lson|1;
if(mulv[o]!=1 || addv[o])push_down(o,l,r,mid,lson,rson);
if(a<=mid)addall(lson,l,mid,a,b,x);
if(b>mid)addall(rson,mid+1,r,a,b,x);
sum[o]=(sum[lson]+sum[rson])%p;
}
}
void mulall(int o,int l,int r,int a,int b,int x){
if(l>=a && r<=b){
mulv[o]=(mulv[o]*x)%p;
addv[o]=(addv[o]*x)%p;
sum[o]=(sum[o]*x)%p;
return;
}
else{
int mid=(l+r)>>1;
int lson=o<<1;
int rson=lson|1;
if(mulv[o]!=1 || addv[o])push_down(o,l,r,mid,lson,rson);
if(a<=mid)mulall(lson,l,mid,a,b,x);
if(b>mid)mulall(rson,mid+1,r,a,b,x);
sum[o]=(sum[lson]+sum[rson])%p;
}
}
long long query(int o,int l,int r,int a,int b){
if(l>=a && r<=b)return sum[o]%p;
else{
int mid=(l+r)>>1;
int lson=o<<1;
int rson=lson|1;
long long ans=0;
if(mulv[o]!=1 || addv[o])push_down(o,l,r,mid,lson,rson);
if(a<=mid)ans+=query(lson,l,mid,a,b);
if(b>mid)ans+=query(rson,mid+1,r,a,b);
return ans%p;
}
}
} tree;
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n,m;
cin>>n>>p;
for(int i=1;i<=n;i++){
cin>>c[i];
}
cin>>m;
tree.build(1,1,n);
for(int i=1;i<=m;i++){
int f;
long long x,y,k;
cin>>f;
if(f==1){
cin>>x>>y>>k;
tree.mulall(1,1,n,x,y,k);
}
else if(f==2){
cin>>x>>y>>k;
tree.addall(1,1,n,x,y,k);
}
else{
cin>>x>>y;
cout<<tree.query(1,1,n,x,y)<<endl;
}
}
return 0;
}
CodeForces718C Sasha and Array
#include <bits/stdc++.h>
#define ls (i<<1)
#define rs (i<<1|1)
#define mid ((l+r)>>1)
#define int long long
using namespace std;
const int MOD = 1e9+7;
struct Matrix{
int a[3][3];
const int size = 2;
Matrix(){
memset(a,0,sizeof(a));
}
Matrix(int aba){
a[aba][aba]=1;
a[aba][aba+1]=0;
a[aba+1][aba]=0;
a[aba+1][aba+1]=1;
}
Matrix(int A,int b,int c,int d){
a[1][1]=A;
a[1][2]=b;
a[2][1]=c;
a[2][2]=d;
}
Matrix operator*(const Matrix &ano) const {
Matrix ans;
for(int i=1;i<=size;i++){
for(int k=1;k<=size;k++){
for(int j=1;j<=size;j++){
ans.a[i][k]=(ans.a[i][k]+a[i][j]*ano.a[j][k])%MOD;
}
}
}
return ans;
}
Matrix operator+(const Matrix aa){
Matrix res;
for(int i=1;i<=size;i++){
for(int j=1;j<=size;j++){
res.a[i][j]=a[i][j]+aa.a[i][j];
res.a[i][j]%=MOD;
}
}
return res;
}
void operator=(const Matrix A){
for(int i=1;i<=size;i++){
for(int j=1;j<=size;j++){
a[i][j]=A.a[i][j];
}
}
}
bool empty(){
return (a[1][1]==0)&&(a[1][2]==0)&&(a[2][1]==0)&&(a[2][2]==0);
}
Matrix operator^(int power){
Matrix res(1);
Matrix base = (*this);
while(power){
if(power&1){
res=res*base;
}
base=base*base;
power>>=1;
}
return res;
}
};
const int SIZE = 1e5+5;
Matrix t[SIZE<<2],tag[SIZE<<2];
int v[SIZE];
const Matrix unit(1);
int n,m;
inline void pushup(int i){
t[i]=t[ls]+t[rs];
}
void build(int i,int l,int r){
tag[i]=unit;
if(l==r){
t[i]=Matrix(1,1,0,0)*(Matrix(1,1,1,0)^(v[l]-1));
return;
}
build(ls,l,mid);
build(rs,mid+1,r);
pushup(i);
}
void pushdown(int i){
if(tag[i].empty()){
return;
}
t[ls]=t[ls]*tag[i];
tag[ls]=tag[ls]*tag[i];
t[rs]=t[rs]*tag[i];
tag[rs]=tag[rs]*tag[i];
tag[i]=unit;
}
void update(int i,int ql,int qr,int l,int r,Matrix x){
if(ql<=l && qr>=r){
t[i]=t[i]*x;
tag[i]=tag[i]*x;
return;
}
pushdown(i);
if(ql<=mid){
update(ls,ql,qr,l,mid,x);
}
if(qr>mid){
update(rs,ql,qr,mid+1,r,x);
}
pushup(i);
}
Matrix query(int i,int ql,int qr,int l,int r){
if(ql<=l && qr>=r){
return t[i];
}
pushdown(i);
Matrix res;
if(ql<=mid){
res = res + query(ls,ql,qr,l,mid);
}
if(qr > mid){
res = res+query(rs,ql,qr,mid+1,r);
}
return res;
}
signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>v[i];
}
build(1,1,n);
while(m--){
int op,l,r,x;
cin>>op;
if(op==1){
cin>>l>>r>>x;
update(1,l,r,1,n,Matrix(1,1,1,0)^x);
}
else{
cin>>l>>r;
cout<<(query(1,l,r,1,n).a[1][2]%MOD)<<'\n';
}
}
return 0;
}
P4145 上帝造题的七分钟 2 / 花神游历各国 | LibreOJ#6281. 数列分块入门 5
注：LibreOJ需要改一改输入。亲测可以AC
#include<bits/stdc++.h>
#define ls(i) (i<<1)
#define rs(i) (i<<1|1)
#define mid(l,r) ((l+r)>>1)
using namespace std;
const int SIZE=100010;
#define int long long
int n,m;
int a[SIZE*4],tag[SIZE*4];
inline void pushup(int t) {
a[t]=a[ls(t)]+a[rs(t)];
tag[t]=max(tag[ls(t)],tag[rs(t)]);
}
void build(int l=1,int r=n,int t=1) {
if(l==r) {
cin>>a[t];
tag[t]=a[t];
return;
}
build(l,mid(l,r),ls(t));
build(mid(l,r)+1,r,rs(t));
pushup(t);
}
void update(int L,int R,int l=1,int r=n,int t=1) {
if(R<l||L>r) return;
if(tag[t]==1) return;
if(l==r) {
tag[t]=a[t]=(int)sqrt(a[t]);
return;
}
update(L,R,l,mid(l,r),ls(t));
update(L,R,mid(l,r)+1,r,rs(t));
pushup(t);
}
int ask(int L,int R,int l=1,int r=n,int t=1) {
if(l>=L&&r<=R) {
return a[t];
}
int ret=0;
if(mid(l,r)>=L) ret+=ask(L,R,l,mid(l,r),ls(t));
if(mid(l,r)<R) ret+=ask(L,R,mid(l,r)+1,r,rs(t));
return ret;
}
signed main() {
cin>>n;
build();
cin>>m;
while(m--) {
int k,l,r;
cin>>k>>l>>r;
if(l>r) swap(l,r);
if(k==0) {
update(l,r);
} else {
cout<<ask(l,r)<<'\n';
}
}
return 0;
}
T218729 mod板 线段树
#include<bits/stdc++.h>
#define int long long
#define ls (now<<1)
#define rs (now<<1|1)
#define mid (l+r>>1)
#define MAX(a,b) (a>b?a:b)
using namespace std;
int n,m;
int a[100001];
int tree[100001<<2],maxn[100001<<2];
inline void pushup(int now) {
tree[now]=tree[ls]+tree[rs];
maxn[now]=MAX(maxn[ls],maxn[rs]);
}
void build(int now,int l,int r) {
if(l==r) {
tree[now]=maxn[now]=a[l];
return ;
}
build(ls,l,mid);
build(rs,mid+1,r);
pushup(now);
}
void update_mod(int now,int l,int r,int x,int y,int mod) {
if(maxn[now]<mod) return ;
if(l==r) {
tree[now]%=mod;
maxn[now]%=mod;
return ;
}
if(mid>=x) {
update_mod(ls,l,mid,x,y,mod);
}
if(mid<y) {
update_mod(rs,mid+1,r,x,y,mod);
}
pushup(now);
}
void update_assign(int now,int l,int r,int x,int k) {
if(l==r) {
tree[now]=maxn[now]=k;
return ;
}
if(mid>=x) {
update_assign(ls,l,mid,x,k);
}
else {
update_assign(rs,mid+1,r,x,k);
}
pushup(now);
}
void update_sqrt(int now,int l,int r,int x,int y) {
if(l==r) {
maxn[now]=tree[now]=sqrt(tree[now]);
return ;
}
if(mid>=x&&maxn[ls]>1) {
update_sqrt(ls,l,mid,x,y);
}
if(mid<y&&maxn[rs]>1){
update_sqrt(rs,mid+1,r,x,y);
}
pushup(now);
}
int query(int now,int l,int r,int x,int y) {
if(l>=x&&r<=y) {
return tree[now];
}
int ret=0;
if(mid>=x) {
ret+=query(ls,l,mid,x,y);
}
if(mid<y) {
ret+=query(rs,mid+1,r,x,y);
}
return ret;
}
signed main() {
cin>>n;
for (int i=1;i<=n;i++) cin>>a[i];
cin>>m;
build(1,1,n);
while(m--) {
int op,l,r,k;
cin>>op;
if(op==1) {
cin>>l>>r;
cout<<query(1,1,n,l,r)<<endl;
}
if(op==2) {
cin>>l>>r;
update_sqrt(1,1,n,l,r);
}
if(op==3) {
cin>>l>>r>>k;
update_mod(1,1,n,l,r,k);
}
if(op==4) {
cin>>l>>k;
update_assign(1,1,n,l,k);
}
}
}
P1801 黑匣子
#include <bits/stdc++.h>
#define ls (i<<1)
#define rs (i<<1|1)
#define mid ((l+r)>>1)
using namespace std;
int c = 1;
const int SIZE = 2e6 + 5;
int t[SIZE << 2];
struct node {
int v, id;
bool operator<(const node ano) const {
return v < ano.v;
}
} a[SIZE];
int u[SIZE];
int mm[SIZE];
int m, n, cnt, I = 1;
void pushup(int i) {
t[i] = t[ls] + t[rs];
}
void update(int p, int i, int l, int r) {
if (l == r && l == p) {
t[i]++;
return;
}
t[i]++;
if (p <= mid) {
update(p, ls, l, mid);
} else {
update(p, rs, mid + 1, r);
}
pushup(i);
}
int query(int p, int i, int l, int r) {
if (l == r) {
return l;
}
if (t[ls] >= p) {
return query(p, ls, l, mid);
} else {
return query(p - t[ls], rs, mid + 1, r);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> m >> n;
for (int i = 1; i <= m; i++) {
cin >> a[i].v;
a[i].id = i;
//cout<<a[i].id<<' '<<a[i].v<<endl;
}
sort(a + 1, a + m + 1);
for (int i = 1; i <= m; i++) {
mm[a[i].id] = i;
}
for (int i = 1; i <= n; i++)cin >> u[i];
for (int i = 1; i <= m; i++) {
//cout<<'\t'<<mm[i]<<endl;
update(mm[i], 1, 1, m);
while (u[c] == i) {
cout << a[query(I, 1, 1, m)].v << '\n';
I++;
c++;
}
}
return 0;
}
P3919 【模板】可持久化线段树 1（可持久化数组）
#include <bits/stdc++.h>
#define ls (i<<1)
#define rs (i<<1|1)
#define mid ((l+r)>>1)
using namespace std;
const int SIZE = 1e6+5;
struct{
int l,r,v; // 线段树节点，存了区间方便搞
}t[SIZE*25];
int top; // 历史版本数
int root[SIZE*25]; // 历史版本根节点位置
int a[SIZE]; // 原始数组
int n,m;
int newnode(int i){ // 新建节点
t[++top]=t[i];
return top;
}
int build(int i,int l,int r){ // 建树
i=(++top); // 建立新版本
if(l==r){
// 叶子节点
t[i].v=a[l];
return i; // 返回当前版本
}
t[i].l=build(t[i].l,l,mid); // 向下递归
t[i].r=build(t[i].r,mid+1,r); // 向下递归
return i; // 返回当前版本
}
int update(int i,int l,int r,int p,int val){
// 单点更新，即数组赋值。
i=newnode(i);
if(l==r){// 叶子节点
t[i].v=val; // 直接更新
return i;// 返回当前版本
}
if(p<=mid){// 向下递归
t[i].l=update(t[i].l,l,mid,p,val);
}
else{// 向下递归
t[i].r=update(t[i].r,mid+1,r,p,val);
}
return i;// 返回当前版本
}
int query(int i,int l,int r,int p){
if(l==r){// 叶子节点
return t[i].v; // 直接返回
}
if(p<=mid){// 向下递归
return query(t[i].l,l,mid,p);
}
else{// 向下递归
return query(t[i].r,mid+1,r,p);
}
}
inline void Assign(int i,int version,int p,int val){
// 封装：在某版本下赋值
root[i]=update(root[version],1,n,p,val);
// 记得新建版本
}
inline int Get(int i,int version,int p){
// 封装：在某版本下取值
root[i]=root[version]; //新建版本
return query(root[version],1,n,p);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
root[0]=build(0,1,n);// 建立原树
for(int i=1,vi,op,loci,valuei;i<=m;i++){
cin>>vi>>op>>loci;
if(op==1){
cin>>valuei;
Assign(i,vi,loci,valuei);
}
else{
cout<<Get(i,vi,loci)<<'\n';
}
}
return 0;
}
P3834 【模板】可持久化线段树 2
#include <bits/stdc++.h>
#define ls (i<<1)
#define rs (i<<1|1)
#define mid ((l+r)>>1)
using namespace std;
const int SIZE = 2e5+5;
struct ArckaAKIOI{
int l,r,v;
ArckaAKIOI(){
l=0,r=0,v=0;
}
}t[SIZE*32];
int top;
int root[SIZE];
int a[SIZE],b[SIZE];
int n,m;
int newnode(int i){
t[++top]=t[i];
return top;
}
int build(int i,int l,int r){
i=(++top);
if(l==r){
t[i].v=a[l];
return i;
}
t[i].l=build(t[i].l,l,mid);
t[i].r=build(t[i].r,mid+1,r);
return i;
}
int update(int i,int l,int r,int p,int val){
i=newnode(i);
t[i].v++;
if(l==r){
return i;
}
if(p<=mid){
t[i].l=update(t[i].l,l,mid,p,val);
}
else{
t[i].r=update(t[i].r,mid+1,r,p,val);
}
return i;
}
int query(int i,int l,int r,int ql,int qr){
if(l==r){
return l;
}
int delta = t[t[qr].l].v-t[t[ql].l].v;
if(delta>=i){
return query(i,l,mid,t[ql].l,t[qr].l);
}
else{
return query(i-delta,mid+1,r,t[ql].r,t[qr].r);
}
}
int kkksc03;
void discretization(){
for(int i=1;i<=n;i++){
b[i]=a[i];
}
sort(b+1,b+1+n);
kkksc03 = unique(b+1,b+n+1)-(b+1);
root[0]=build(0,1,kkksc03);
for(int i=1;i<=n;i++){
root[i]=update(root[i-1],1,kkksc03,lower_bound(b+1,b+kkksc03+1,a[i])-b,114514);
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
discretization();
while(m--){
int l,r,k;
cin>>l>>r>>k;
cout<<b[query(k,1,kkksc03,root[l-1],root[r])]<<'\n';
}
return 0;
}
SP3946 MKTHNUM - K-th Number
#include <bits/stdc++.h>
#define ls (i<<1)
#define rs (i<<1|1)
#define mid ((l+r)>>1)
using namespace std;
const int SIZE = 100005;
struct ArckaAKIOI{
int l,r,v;
ArckaAKIOI(){
l=0,r=0,v=0;
}
}t[SIZE<<5];
int top;
int root[SIZE<<5];
int a[SIZE],b[SIZE];
int n,m;
int newnode(int i){
t[++top]=t[i];
return top;
}
int build(int i,int l,int r){
i=(++top);
if(l==r){
t[i].v=a[l];
return i;
}
t[i].l=build(t[i].l,l,mid);
t[i].r=build(t[i].r,mid+1,r);
return i;
}
int update(int i,int l,int r,int p,int val){
i=newnode(i);
t[i].v++;
if(l==r){
return i;
}
if(p<=mid){
t[i].l=update(t[i].l,l,mid,p,val);
}
else{
t[i].r=update(t[i].r,mid+1,r,p,val);
}
return i;
}
int query(int i,int l,int r,int ql,int qr){
if(l==r){
return l;
}
int delta = t[t[qr].l].v-t[t[ql].l].v;
if(delta>=i){
return query(i,l,mid,t[ql].l,t[qr].l);
}
else{
return query(i-delta,mid+1,r,t[ql].r,t[qr].r);
}
}
int kkksc03;
void discretization(){
for(int i=1;i<=n;i++){
b[i]=a[i];
}
sort(b+1,b+1+n);
kkksc03 = unique(b+1,b+n+1)-(b+1);
root[0]=build(0,1,kkksc03);
for(int i=1;i<=n;i++){
root[i]=update(root[i-1],1,kkksc03,lower_bound(b+1,b+kkksc03+1,a[i])-b,114514);
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
discretization();
while(m--){
int l,r,k;
cin>>l>>r>>k;
cout<<b[query(k,1,kkksc03,root[l-1],root[r])]<<'\n';
}
return 0;
}
P3224 [HNOI2012]永无乡| BZOJ2733 [HNOI2012]永无乡
#include <bits/stdc++.h>
#define mid ((l+r)>>1)
using namespace std;
int n, m, cnt, q;
const int SIZE = 1e6 + 5;
struct {
int fa[SIZE];
void init(int n) {
for (int i = 1; i <= n; i++) {
fa[i] = i;
}
}
int find(int x) {
if (fa[x] == x)return x;
else return fa[x] = find(fa[x]);
}
void merge(int x, int y) {
fa[x] = y;
}
} uf;
struct node {
int l, r, v;
} t[SIZE << 2];
int kkk[SIZE],a[SIZE],root[SIZE];
void newnode(int &i, int l, int r, int p) {
if (!i) {
i = (++cnt);
}
t[i].v++;
if (l == r)return;
if (p <= mid) {
newnode(t[i].l, l, mid, p);
} else {
newnode(t[i].r, mid + 1, r, p);
}
}
void merge(int &a, int &b) {
if (!a) {
a = b;
} else if (!b) {}
else {
t[a].v += t[b].v;
merge(t[a].l, t[b].l);
merge(t[a].r, t[b].r);
}
}
int query(int i,int l,int r,int p){
if(l==r){
return kkk[l];
}
int lsum = t[t[i].l].v;
if(p<=lsum){
return query(t[i].l,l,mid,p);
}
else{
return query(t[i].r,mid+1,r,p-lsum);
}
}
int main() {
cin>>n>>m;
uf.init(n);
for(int i=1;i<=n;i++){
cin>>a[i];
kkk[a[i]]=i;
newnode(root[i],1,n,a[i]);
}
while(m--){
int x,y;
cin>>x>>y;
merge(root[uf.find(y)],root[uf.find(x)]);
uf.merge(uf.find(x),uf.find(y));
}
cin>>q;
for(int i=1,x,y;i<=q;i++){
char op[1145];
cin>>op;
cin>>x>>y;
if(op[0]=='B'){
merge(root[uf.find(y)],root[uf.find(x)]);
uf.merge(uf.find(x),uf.find(y));
}
else{
if(t[root[uf.find(x)]].v<y){
cout<<-1<<'\n';
}
else{
cout<<query(root[uf.find(x)],1,n,y)<<'\n';
}
}
}
return 0;
}
最新文章
- [Django]用户权限学习系列之设计自有权限管理系统设计思路
- php、前端开发（网站建设）环境搭建
- 滚动监听（bootstrap）
- 服务器程序DEBUG
- js原型继承的几种方式
- bat命令
- 基于tcp/udp的协议
- python BDD 框架之lettuce
- JAVA安卓和C# 3DES加密解密的兼容性问题(2013年8月修改版)
- linux网卡混杂模式打开
- ubuntu各版本的区别
- 11g默认审计选项
- jacoco统计server端功能测试覆盖率
- 【BZOJ3809】Gty的二逼妹子序列 莫队 分块
- Hadoop ConnectException: Connection refused的一种解决办法
- Latex 公式颜色
- hadoop备战：yarn框架的搭建（mapreduce2）
- Unity3D学习笔记（二十二）：ScrollView和事件接口
- sqlserver存储过程循环写法
- 可以嵌入程序的chrome