# Codeforces Round #771 (Div. 2) E Colorful Operations()-opera

## Codeforces Round #771 (Div. 2) E Colorful Operations()

Colorful Operations

``a->b``

``````#include <iostream>
#include <cstdio>
#include <vector>
#include <set>
using namespace std;
typedef long long ll;
#define It set<ran>::iterator
vector<ll>tr, tag;
int n, m;

inline int lowbit(int x)
{
return x & (-x);
}

{
for(int i=x; i<=n; i+=lowbit(i))
tr[i] += w;
}

void update(int l, int r, ll w)
{
}

ll query(int x)
{
ll ans = 0;
for(int i=x; i; i-=lowbit(i))
ans += tr[i];
return ans;
}

struct ran
{
int l, r;
mutable ll w;
ran(){}
ran(int _l, int _r, ll _w){l = _l; r = _r; w = _w;}
bool operator < (const ran& x) const
{
return l < x.l;
}
};

set<ran>st;
It split(int pos)
{
It now = st.lower_bound(ran(pos, -1, 0));
if(now != st.end() && now->l == pos) return now;
now--;
int l = now->l, r = now->r;
ll w = now->w;
st.erase(now);
st.insert(ran(l, pos - 1, w));
return st.insert(ran(pos, r, w)).first;
}

void merge_update(int l, int r, int w)
{
It itr = split(r + 1), itl = split(l);
for(It it=itl; it!=itr; it++)
update(it->l, it->r, tag[it->w]);
st.erase(itl, itr);
update(l, r, -tag[w]);
st.insert(ran(l, r, w));
}

ll Query(int x)
{
It it = st.lower_bound(ran(x, -1, 0));
if(it == st.end() || it->l != x) it--;
return tag[it->w] + query(x);
}

int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
tr.resize(n + 1, 0);
tag.resize(n + 1, 0);
st.insert(ran(1, n, 1));
while(m--)
{
string op;
cin >> op;
if(op == "Color")
{
int l, r, c;
cin >> l >> r >> c;
merge_update(l, r, c);
}
{
int c, x;
cin >> c >> x;
tag[c] += x;
}
else
{
int i;
cin >> i;
cout << Query(i) << "\n";
}
}
return 0;
}
``````
————————

Colorful Operations

``a->b``

``````#include <iostream>
#include <cstdio>
#include <vector>
#include <set>
using namespace std;
typedef long long ll;
#define It set<ran>::iterator
vector<ll>tr, tag;
int n, m;

inline int lowbit(int x)
{
return x & (-x);
}

{
for(int i=x; i<=n; i+=lowbit(i))
tr[i] += w;
}

void update(int l, int r, ll w)
{
}

ll query(int x)
{
ll ans = 0;
for(int i=x; i; i-=lowbit(i))
ans += tr[i];
return ans;
}

struct ran
{
int l, r;
mutable ll w;
ran(){}
ran(int _l, int _r, ll _w){l = _l; r = _r; w = _w;}
bool operator < (const ran& x) const
{
return l < x.l;
}
};

set<ran>st;
It split(int pos)
{
It now = st.lower_bound(ran(pos, -1, 0));
if(now != st.end() && now->l == pos) return now;
now--;
int l = now->l, r = now->r;
ll w = now->w;
st.erase(now);
st.insert(ran(l, pos - 1, w));
return st.insert(ran(pos, r, w)).first;
}

void merge_update(int l, int r, int w)
{
It itr = split(r + 1), itl = split(l);
for(It it=itl; it!=itr; it++)
update(it->l, it->r, tag[it->w]);
st.erase(itl, itr);
update(l, r, -tag[w]);
st.insert(ran(l, r, w));
}

ll Query(int x)
{
It it = st.lower_bound(ran(x, -1, 0));
if(it == st.end() || it->l != x) it--;
return tag[it->w] + query(x);
}

int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
tr.resize(n + 1, 0);
tag.resize(n + 1, 0);
st.insert(ran(1, n, 1));
while(m--)
{
string op;
cin >> op;
if(op == "Color")
{
int l, r, c;
cin >> l >> r >> c;
merge_update(l, r, c);
}
{
int c, x;
cin >> c >> x;
tag[c] += x;
}
else
{
int i;
cin >> i;
cout << Query(i) << "\n";
}
}
return 0;
}
``````