:::spoiler `cses1649`
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define REP(i,N) for( int i = 0; i < N; ++i)
#define FOR(i,a,b) for( int i = (a); i <= (b); ++i )
template<typename T>
using V = vector<T>;
constexpr int INF = int(1e9+1);
mt19937 rd;
struct Treap{
struct node {
node*l,*r;
int val, mn, pri, sz;
node(int _val) : val(_val), mn(_val),pri(rd()), sz(1){l = r = nullptr;};
void pull() {
mn = min( {l?l->mn:INF, r?r->mn:INF, val} );
sz = (l?l->sz:0) + (r?r->sz:0) + 1;
}
void push() {}
}*root= nullptr;
node* merge( node*a, node*b ) {
if( a ) a->push();
if( b ) b->push();
if( !a || !b ) return (a ? a : b);
if( a->pri > b->pri )
return a->r = merge(a->r, b), a->pull(),a;
else
return b->l = merge(a, b->l), b->pull(),b;
}
int size(node*cur){return (cur?cur->sz:0);}
void split( node*cur, node*&a, node*&b, int pos){
if( !cur ) return a = b = nullptr, void();
cur->push();
if( pos <= size(cur->l) )
b=cur, split(cur->l, a, b->l, pos);
else
a=cur, split(cur->r, a->r, b, pos-size(cur->l)-1);
cur->pull();
}
void insert( int _val) {
root = merge( root, new node(_val));
}
void modify( int pos, int _val ) {
node*a, *b,*c;
split( root, b, c, pos );
split( b, a, b, pos-1 );
b->val = b->mn = _val;
root = merge( a, merge(b, c ));
}
int query( int l, int r ) {
node*a,*b,*c;
split( root, b, c, r);
split( b, a, b, l-1 );
int ans = b->mn;
root = merge(a, merge(b,c));
return ans;
}
};
void solve() {
int N, Q; cin >> N >> Q;
Treap tree;
REP(i,N) {
int a; cin >> a;
tree.insert( a );
}
REP(i, Q) {
int md; cin >> md;
if( md == 1 ) {
int k, u; cin >> k >> u;
tree.modify( k, u );
}
if( md == 2 ) {
int a, b; cin >> a >> b;
cout << tree.query( a, b ) << '\n';
}
}
}
int main () {
int T = 1;
#ifdef LOCAL
freopen("input.txt", "r", stdin );
freopen("output.txt", "w", stdout);
cin >> T;
#endif
while(T--) solve();
}
```
:::
:::spoiler `cses1735`
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for( int i = (a); i <= (b); ++i)
#define REP(i,N) for(int i=0;i<N;++i)
#pragma GCC optimize("O2")
using ll = long long;
template<typename T>
using V = vector<T>;
mt19937 rd;
struct Treap {
struct node {
node*l,*r;
ll tag, tag_val, sum, val, pri;
int sz;
node(int _val) : tag(0), tag_val(0), sum(_val), val(_val), pri(rd()), sz(1) {l=r=nullptr;}
void push(){
if( !tag ) return;
if( tag == 1 ) {
sum += tag_val * sz;
val += tag_val;
if( l ) {
if( !l->tag ) l->tag = 1;
l->tag_val += tag_val;
}
if( r ) {
if( !r->tag ) r->tag = 1;
r->tag_val += tag_val;
}
}
if( tag == 2 ) {
val = tag_val;
sum = tag_val * sz;
if( l )
l->tag=2, l->tag_val=tag_val;
if( r )
r->tag=2, r->tag_val=tag_val;
}
tag = tag_val = 0;
};
void pull() {
sum = val;
if( l ) {
if( l->tag <= 1 ) sum += l->sum + (l->tag_val * l->sz);
if( l->tag == 2 ) sum += (l->tag_val * l->sz );
}
if( r ) {
if( r->tag <= 1 ) sum += r->sum + (r->tag_val * r->sz );
if( r->tag == 2 ) sum += (r->tag_val * r->sz );
}
sz = (l?l->sz:0) + (r?r->sz:0) + 1;
}
}*root = nullptr;
node*merge( node*a, node*b) {
if( !a || !b ) return (a ? a : b);
a->push(); b->push();
if( a->pri > b->pri )
return a->r = merge(a->r, b), a->pull(),a;
else
return b->l = merge(a, b->l), b->pull(),b;
}
int size(node*cur){return (cur?cur->sz:0);}
void split(node*cur, node*&a, node*&b, int pos ) {
if( !cur ) return a = b = nullptr, void();
cur->push();
if( pos <= size(cur->l) )
b=cur,split(cur->l,a,b->l,pos);
else
a=cur,split(cur->r,a->r,b,pos-size(cur->l)-1);
cur->pull();
}
void insert( int _val ) {
root = merge( root, new node(_val));
}
void update( int l, int r, int val, int md ) {
node*a,*b,*c;
split(root, b, c, r);
split(b,a,b,l-1);
b->tag = md;
b->tag_val += val;
root = merge( a, merge(b, c ));
}
ll query( int l, int r ) {
node*a,*b,*c;
split(root,b,c,r);
split(b,a,b,l-1);
ll ans = b->sum;
root = merge(a,merge(b,c));
return ans;
}
};
void solve() {
int N, Q; cin >> N >> Q;
Treap tree;
REP(i,N) {
int a; cin >> a;
tree.insert( a );
}
//cout << tree.root->sz << '\n';
REP(i, Q) {
int md; cin >> md;
if( md <= 2 ) {
int a, b, x; cin >> a >> b >> x;
tree.update( a, b, x, md);
}
if( md== 3 ) {
int a, b;
cin >> a >> b;
cout << tree.query( a, b ) << '\n';
}
}
}
int main () { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int T = 1;
#ifdef LOCAL
freopen("intput.txt", "r", stdin);
freopen("output.txt", "w", stdout);
cin >>T;
#endif
while(T--) solve();
}
```
:::
:::spoiler `cses2072`
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define REP(i,N) for( int i = 0; i < (N); ++ i)
#define FOR(i,a,b) for( int i = (a); i <= (b); ++i)
mt19937 rd;
struct Treap {
struct node {
node*l,*r;
int val, sz, pri;
node(int _val) : val(_val), sz(1), pri(rd()) {l=r=nullptr;}
void pull() {
sz = (l?l->sz:0) + (r?r->sz:0) + 1;
}
}*root = nullptr;
node* merge( node*a, node*b) {
if( !a || !b ) return (a?a:b);
if( a->pri > b->pri )
return a->r=merge(a->r, b), a->pull(), a;
else
return b->l=merge(a, b->l), b->pull(), b;
}
int size(node*cur){return cur?cur->sz:0;}
void split( node*cur, node*&a, node*&b, int pos) {
if( !cur ) return a = b = nullptr, void();
if( pos <= size(cur->l) )
b=cur, split(cur->l, a, b->l, pos );
else
a=cur, split(cur->r, a->r, b, pos-size(cur->l)-1);
cur->pull();
}
void insert( int _val ) {
root = merge(root, new node(_val));
}
void pasteToEnd( int l, int r ) {
node*a,*b,*c;
split(root, b, c, r);
split(b,a,b,l-1);
root = merge( a, merge(c, b));
}
void getAns( node*cur, string&ans) {
if( !cur ) return;
getAns( cur->l, ans );
ans += cur->val + 'A';
getAns(cur->r, ans);
}
void getAns( string &ans ) {getAns( root, ans);};
};
void solve() {
int N, M; cin >> N >> M;
Treap tree;
REP(i,N) {
char c;
cin >> c;
tree.insert( c-'A' );
}
REP(i, M) {
int a, b;
cin >> a >> b;
tree.pasteToEnd(a,b);
}
string ans;
tree.getAns(ans);
cout << ans << '\n';
}
int main () {
int T = 1;
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
cin>>T;
#endif
while(T--) solve();
}
```
:::
:::spoiler `cses2073`
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for( int i = (a); i <= (b); ++i)
#define REP(i,N) for(int i=0;i<N;++i)
#pragma GCC optimize("O2")
using ll = long long;
template<typename T>
using V = vector<T>;
mt19937 rd;
struct Treap {
struct node {
node*l,*r;
ll tag, tag_val, sum, val, pri;
int sz;
node(int _val) : tag(0), tag_val(0), sum(_val), val(_val), pri(rd()), sz(1) {l=r=nullptr;}
void push(){
if( !tag ) return;
if( tag == 1 ) {
sum += tag_val * sz;
val += tag_val;
if( l ) {
if( !l->tag ) l->tag = 1;
l->tag_val += tag_val;
}
if( r ) {
if( !r->tag ) r->tag = 1;
r->tag_val += tag_val;
}
}
if( tag == 2 ) {
val = tag_val;
sum = tag_val * sz;
if( l )
l->tag=2, l->tag_val=tag_val;
if( r )
r->tag=2, r->tag_val=tag_val;
}
tag = tag_val = 0;
};
void pull() {
sum = val;
if( l ) {
if( l->tag <= 1 ) sum += l->sum + (l->tag_val * l->sz);
if( l->tag == 2 ) sum += (l->tag_val * l->sz );
}
if( r ) {
if( r->tag <= 1 ) sum += r->sum + (r->tag_val * r->sz );
if( r->tag == 2 ) sum += (r->tag_val * r->sz );
}
sz = (l?l->sz:0) + (r?r->sz:0) + 1;
}
}*root = nullptr;
node*merge( node*a, node*b) {
if( !a || !b ) return (a ? a : b);
a->push(); b->push();
if( a->pri > b->pri )
return a->r = merge(a->r, b), a->pull(),a;
else
return b->l = merge(a, b->l), b->pull(),b;
}
int size(node*cur){return (cur?cur->sz:0);}
void split(node*cur, node*&a, node*&b, int pos ) {
if( !cur ) return a = b = nullptr, void();
cur->push();
if( pos <= size(cur->l) )
b=cur,split(cur->l,a,b->l,pos);
else
a=cur,split(cur->r,a->r,b,pos-size(cur->l)-1);
cur->pull();
}
void insert( int _val ) {
root = merge( root, new node(_val));
}
void update( int l, int r, int val, int md ) {
node*a,*b,*c;
split(root, b, c, r);
split(b,a,b,l-1);
b->tag = md;
b->tag_val += val;
root = merge( a, merge(b, c ));
}
ll query( int l, int r ) {
node*a,*b,*c;
split(root,b,c,r);
split(b,a,b,l-1);
ll ans = b->sum;
root = merge(a,merge(b,c));
return ans;
}
};
void solve() {
int N, Q; cin >> N >> Q;
Treap tree;
REP(i,N) {
int a; cin >> a;
tree.insert( a );
}
//cout << tree.root->sz << '\n';
REP(i, Q) {
int md; cin >> md;
if( md <= 2 ) {
int a, b, x; cin >> a >> b >> x;
tree.update( a, b, x, md);
}
if( md== 3 ) {
int a, b;
cin >> a >> b;
cout << tree.query( a, b ) << '\n';
}
}
}
int main () { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int T = 1;
#ifdef LOCAL
freopen("intput.txt", "r", stdin);
freopen("output.txt", "w", stdout);
cin >>T;
#endif
while(T--) solve();
}
```
:::
Sign in with Wallet
Connect another wallet