Untitled
unknown
plain_text
3 years ago
11 kB
6
Indexable
/*Its foolish to fear what we have yet to see and know*/
#pragma GCC optimize "trapv"
#include <bits/stdc++.h>
// #include<ext/pb_ds/assoc_container.hpp>
// #include<ext/pb_ds/tree_policy.hpp>
using namespace std;
// using namespace __gnu_pbds;
// typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
// find_by_order(k) returns iterator to kth element starting from 0;
// order_of_key(k) returns count of elements strictly smaller than k;
#define FAST ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define count_1(n) __builtin_popcountll(n)
#define pb push_back
#define fr(a,b) for(int i =a ;i <b ;i++)
#define all(x) (x).begin(), (x).end()
#define vint vector<int>
typedef long long ll;
typedef long double ld;
const int N = 1e9 + 7 ;
#define inf (1LL<<62)
template <typename T>istream &operator>>(istream &istream, vector<T> &vec){for (auto &a : vec)cin >> a;return istream;}
template <typename T>ostream &operator<<(ostream &ostream, const vector<T> &vec){for (auto &a : vec)cout << a << " ";return ostream;}
long long binpow(long long a, long long b, long long m) {
a %= m;
long long res = 1;
while (b > 0) {
if (b & 1)
res = res * a % m;
a = a * a % m;
b >>= 1;
}
return res;
}
//#define int long long
vint dx = {0,+1,0,-1} ;
vint dy = {1,0,-1,0} ;
int msb(int value){
if(value==0) return 0;
int count=0;
while(value>>count){
count++;
}
return count;
}
#define int ll
ll nCr(int n, int r){ ll p = 1, k = 1;if (n - r < r) {r = n - r;}
if (r != 0) {while (r) {p *= n;k *= r; ll m = __gcd(p, k);p /= m;k /= m;n--;r--;}}
else {p = 1;} return p;}
struct segmenttree {
int n;
vector<int> st;
vector<pair<int,int>> lazy ;
//{add itna , replace each by itna}
void init(int _n) {
this->n = _n;
st.resize(4 * n, 0);
lazy.resize(4 * n, {0,0});
}
void build(int start, int ending, int node, vector<int> &v) {
// leaf node base case
if (start == ending) {
st[node] = v[start];
return;
}
int mid = (start + ending) / 2;
// left subtree is (start,mid)
build(start, mid, 2 * node + 1, v);
// right subtree is (mid+1,ending)
build(mid + 1, ending, 2 * node + 2, v);
st[node] = st[node * 2 + 1] + st[node * 2 + 2];
}
int query(int start, int ending, int l, int r, int node) {
// non overlapping case
if (r < start || ending < l) {
return 0;
}
// lazy propagation / clear the lazy update
if (lazy[node].first != 0 || lazy[node].second != 0) {
// pending updates
// update the segment tree node
//if(a range has to be replaced by a certain value )
if(lazy[node].second != 0) st[node] = lazy[node].second * (ending - start + 1) ;
st[node] += lazy[node].first * (ending - start + 1);
if (start != ending) {
// propagate the updated value
if(lazy[node].second == 0){
lazy[2 * node + 1].first += lazy[node].first;
lazy[2 * node + 2].first += lazy[node].first;
}else{
lazy[2 * node + 1].second = lazy[node].second ;
lazy[2 * node + 2].second = lazy[node].second ;
lazy[2 * node + 1].first = lazy[node].first;
lazy[2 * node + 2].first = lazy[node].first;
}
}
lazy[node] = {0,0};
}
// complete overlap
if (start >= l && ending <= r) {
return st[node];
}
// partial case
int mid = (start + ending) / 2;
int q1 = query(start, mid, l, r, 2 * node + 1);
int q2 = query(mid + 1, ending, l, r, 2 * node + 2);
// st[node] = st[node * 2 + 1] + st[node * 2 + 2];
return q1 + q2;
}
void update(int start, int ending, int node, int l, int r, int additta , int replaceitta) {
// non overlapping case
if (start > r || ending < l) {
return ;
}
// lazy propagation / clear the lazy update
if (lazy[node].first != 0 || lazy[node].second !=0 ) {
// pending updates
// update the segment tree node
//if(a range has to be replaced by a certain value )
if(lazy[node].second != 0)st[node] = lazy[node].second* (ending - start + 1) ;
st[node] += lazy[node].first * (ending - start + 1);
if (start != ending) {
// propagate the updated value
if(lazy[node].second == 0){
lazy[2 * node + 1].first += lazy[node].first;
lazy[2 * node + 2].first += lazy[node].first;
}else{
lazy[2 * node + 1].second = lazy[node].second ;
lazy[2 * node + 2].second = lazy[node].second ;
lazy[2 * node + 1].first = lazy[node].first;
lazy[2 * node + 2].first = lazy[node].first;
}
}
lazy[node] = {0,0};
}
// complete overlap
if (start >= l && ending <= r) {
if(additta == 0){
lazy[node].first = 0 ;
lazy[node].second = replaceitta ;
}else{
lazy[node].first = additta ;
//lazy[node].second = 0 ;
}
if(lazy[node].second != 0)st[node] = lazy[node].second* (ending - start + 1) ;
st[node] += lazy[node].first * (ending - start + 1);
if (start != ending) {
// propagate the updated value
if(lazy[node].second == 0){
lazy[2 * node + 1].first += lazy[node].first;
lazy[2 * node + 2].first += lazy[node].first;
}else{
lazy[2 * node + 1].second = lazy[node].second ;
lazy[2 * node + 2].second = lazy[node].second ;
lazy[2 * node + 1].first = lazy[node].first;
lazy[2 * node + 2].first = lazy[node].first;
}
}
lazy[node] = {0,0};
return;
}
// partial case
int mid = (start + ending) / 2;
update(start, mid, 2 * node + 1, l, r, additta , replaceitta);
update(mid + 1, ending, 2 * node + 2, l, r, additta , replaceitta);
st[node] = st[node * 2 + 1] + st[node * 2 + 2];
return;
}
void build(vector<int> &v) {
build(0, n - 1, 0, v);
}
int query(int l, int r) {
return query(0, n - 1, l, r,0);
}
void update(int l, int r, int x, int y) {
update(0, n - 1, 0, l, r, x , y);
}
};
signed main() {
FAST
ll t,n,m,x,i,j,k,q ;
t=1;
// cin >>t ;
while(t--){
cin >>n >> q ;
vint v(n) ;
cin >> v ;
segmenttree ss ;
ss.init(n) ;
ss.build(v) ;
fr(0,q){
int a , b, c ,d;
cin >>a >> b >> c ;
b-- ; c--;
if(a==1){
cin >>d ;
ss.update(b,c,d,0) ;
}else if(a==2){
cin >>d ;
ss.update(b,c,0,d) ;
}else{
cout << ss.query(b,c)<<"\n" ;
}
}
}
return 0;
}
/*Parent info ke lie its better to have use dfs
Return in build base biro :)
10^9 is within integer limits
string c1(1,s1[0]) ;
cout<<setw(2)<<setfill('0')<<a;
*/
/* //DIJKSTRAS ;
vector<pair<int,int>> g[n+1] ;
vector<int> lev(n+1,INF) ;
for(int i=0;i<m;i++){
int x,y ;
cin >> x >> y ;
g[x].push_back({y,0}) ;
g[y].push_back({x,1}) ;
}
lev[1] =0 ;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q ;
q.push({0,1}) ;
while(!q.empty()){
int wt = q.top().first ;
int x = q.top().second ;
q.pop() ;
if(lev[x] < wt )continue ;
for(auto cur : g[x]){
int c=cur.first ;
int d= cur.second ;
if(lev[c] > wt+d){
lev[c] = wt+d ;
q.push({lev[c],c}) ;
}
}
}
*/
/*int modInverse(int a, int m)
{
int m0 = m;
int y = 0, x = 1;
if (m == 1)
return 0;
while (a > 1) {
int q = a / m;
int t = m;
m = a % m, a = t;
t = y;
y = x - q * y;
x = t;
}
*/
/* //BL & LCA
vint adj[200005] ;
int depth[200005] ;
int parent[30][200005] ;
void dfs(int node, int par){
for(auto child : adj[node]){
if( child != par){
parent[0][child] = node ;
depth[child] = depth[node] +1 ;
dfs(child , node) ;
}
}
}
int raise(int x , int y){
int z =0 ;
while(y > 0){
if(y&1) x = parent[z][x] ;
y >>= 1 ;
z++ ;
}
return x ;
}
int lca(int x , int y){
if(depth[x] > depth[y]) swap(x,y) ;
int z = depth[y] - depth[x] ;
y = raise(y,z) ;
if(x== y) return x ;
for(int i =29 ;i >= 0 ;i--){
if(parent[i][x] != parent[i][y]){
x = parent[i][x] ;
y = parent[i][y] ;
}
}
return parent[0][x] ;
//HMMMMMMMMMMMMMMMMMMMMMMMMM
fr(0,n-1){
int a, b ;
cin >> a >> b ;
adj[a].pb(b) ;
adj[b].pb(a) ;
}
dfs(1,0) ;
fr(1,30){
for(int j = 1 ; j <= n ;j++){
parent[i][j] = parent[i-1][parent[i-1][j]] ;
}
}
}
*/
/*
struct segmenttree {
int n;
vector<int> st;
void init(int _n) {
this->n = _n;
st.resize(4 * n, 0);
}
void build(int start, int ending, int node, vector<int> &v) {
// leaf node base case
if (start == ending) {
st[node] = v[start];
return;
}
int mid = (start + ending) / 2;
// left subtree is (start,mid)
build(start, mid, 2 * node + 1, v);
// right subtree is (mid+1,ending)
build(mid + 1, ending, 2 * node + 2, v);
st[node] = st[node * 2 + 1] ^ st[node * 2 + 2];
}
int query(int start, int ending, int l, int r, int node) {
// non overlapping case
if (start > r || ending < l) {
return 0;
}
// complete overlap
if (start >= l && ending <= r) {
return st[node];
}
// partial case
int mid = (start + ending) / 2;
int q1 = query(start, mid, l, r, 2 * node + 1);
int q2 = query(mid + 1, ending, l, r, 2 * node + 2);
return q1 ^ q2;
}
void update(int start, int ending, int node, int index, int value) {
// base case
if (start == ending) {
st[node] = value;
return;
}
int mid = (start + ending) / 2;
if (index <= mid) {
// left subtree
update(start, mid, 2 * node + 1, index, value);
}
else {
// right
update(mid + 1, ending, 2 * node + 2, index, value);
}
st[node] = st[node * 2 + 1] + st[node * 2 + 2];
return;
}
void build(vector<int> &v) {
build(0, n - 1, 0, v);
}
int query(int l, int r) {
return query(0, n - 1, l, r, 0);
}
void update(int x, int y) {
update(0, n - 1, 0, x, y);
}
};
*/
/*class DSU{
public:
vector<int>parent;
DSU(int n) { parent.resize(n+1); for(int i=0;i<=n;i++) parent[i]=-1; }
int find_set(int x) { return parent[x]<0?x:parent[x]=find_set(parent[x]); }
bool union_set(int a,int b){ int pa=find_set(a); int pb=find_set(b);
if(pa==pb) { return 0; } if(parent[pa]>parent[pb]) { swap(pa,pb); }
parent[pa]+=parent[pb]; parent[pb]=pa; return 1; }
bool same_set(int a,int b){ return find_set(a)==find_set(b); } };
*/
/*
cin >> n >> m >> sx >> sy >> d ;
int d1 = (max(1,sx-d)-1)&(sy-1) ;
int d2 = (sx-1)&(max(1,sy-d)-1) ;
int d3 = (min(n,sx+d)-n)&(sy-m) ;
int d4 =(sx-n)&(min(m,sy+d)-m) ;
if((d1==0 && d2==0)||(d1==0 && d3==0)||(d4==0 && d2==0)||(d3==0 && d4==0)){
cout <<(n+m)-2 <<"\n" ;
}else{
cout <<"-1" <<"\n" ;
}
*/Editor is loading...