奇搜建设辽沈阳网站,电商出口营销要多少钱,打广告网站,安卓手机app开发工具文章目录题意#xff1a;思路#xff1a;传送门
题意#xff1a;
给你一个数组aaa#xff0c;初始价值全为000#xff0c;颜色全为111#xff0c;让后让你实现以下三个操作#xff1a;
将[l,r][l,r][l,r]区间内的颜色都染成ccc。将所有颜色为ccc的位置价值都加上xxx。…
文章目录题意思路传送门
题意
给你一个数组aaa初始价值全为000颜色全为111让后让你实现以下三个操作
将[l,r][l,r][l,r]区间内的颜色都染成ccc。将所有颜色为ccc的位置价值都加上xxx。询问iii位置的价值。
1≤n,q≤1e61\le n,q\le 1e61≤n,q≤1e6
思路
首先分析一下第二个操作是全局的这就提示我们每次执行第二个操作的时候可以打一个懒标记lazy[c]xlazy[c]xlazy[c]x当询问某个点的价值的时候只需要输出ailazy[c]a_ilazy[c]ailazy[c]即可ccc为当前点的颜色。
但是这都是不考虑第一个操作的情况下的考虑第一个操作假设lrlrlr我们将他分为两个步骤
首先将当前位置原本的颜色c′cc′对应的lazy[c′]lazy[c]lazy[c′]加到ala_lal上。将当前颜色改成ccc。
上述步骤很明显有一个问题就是将修改前的lazy[c]lazy[c]lazy[c]的代价在第三个操作的时候也算进去了这显然是不对的不过我们发现可以在第二部中将al−lazy[c]a_l-lazy[c]al−lazy[c]这样就可以消除上述多余的价值了。
我们解决了单个的再来看区间的怎么搞。
直接暴力不可以但是我们不难发现可以将其拆分成若干个区间每个区间的颜色都相同类似与珂朵莉树保证都是推平操作的话区间个数下降的很快的这样我们只需要用setsetset维护这些区间让后快速找到并且可以遍历这些区间修改他们让后将他们推平这看似暴力的算法实际平摊下来是O(q)O(q)O(q)的由于对于每个区间我们还需要实现区间加某个数显然BITBITBIT就可以实现总复杂度是O(qlogn)O(qlogn)O(qlogn)。
#includebits/stdc.h
#define Mid (tr[u].ltr[u].r1)
#define pb push_back
#define IT setnode::iterator
#define x first
#define y second
using namespace std;const int N2000010,INF0x3f3f3f3f,mod1e97;
typedef long long LL;
typedef pairLL,LL PII;int n,m;
LL a[N];
vectorPIIv[N];struct node
{int l,r,t;mutable int v;bool operator (const node o) const {return lo.l;}
};
setnodes;int find(int col,int t) {int l0,r(int)v[col].size()-1,ans-1;if(r-1) return INF;while(lr) {int midlr1;if(v[col][mid].yt) ansmid,lmid1;else rmid-1;}return ans;
}struct BIT {LL tr[N];#define lowbit(x) (x(-x))void add(int x,LL c) {for(int ix;iN;ilowbit(i)) tr[i]c;}LL sum(int x) {LL ans0;for(int ix;i;i-lowbit(i)) anstr[i];return ans;}
}bit;IT splitl(int pos) {IT its.upper_bound({pos,-1,-1,-1});--it;return it;
}IT splitr(int pos) {IT its.upper_bound({pos,-1,-1,-1});return it;
}void add(int l,int r,int c,int t) {IT itrsplitr(r1);IT itlsplitl(l);for(;itl!itr;itl) {int lsitl-l,rsitl-r;lsmax(ls,l);rsmin(rs,r);int colitl-v,titl-t;int posfind(col,t);if(pos!INF) {LL edv[col].back().x;if(pos!-1) ed-v[col][pos].x;bit.add(rs1,-ed); bit.add(ls,ed);}}itlsplitl(l);node ls,rs;ls.l-1; rs.l-1;if(itl-ll) {ls.litl-l; ls.rl-1;ls.vitl-v; ls.titl-t;}if(itl-rr) {rs.lr1; rs.ritl-r;rs.vitl-v; rs.titl-t;}itr--;if(itr-rr) {rs.lr1; rs.ritr-r;rs.vitr-v; rs.titr-t;}itr;s.erase(itl,itr);if(ls.l!-1) s.insert(ls);if(rs.l!-1) s.insert(rs);s.insert({l,r,t,c});
}LL query(int pos) {IT nowsplitl(pos);int tnow-t,colnow-v;posfind(col,t);LL ans0;if(pos!INF) {LL edv[col].back().x;if(pos!-1) ed-v[col][pos].x;ansed;}return ans;
}void solve() {scanf(%d%d,n,m);s.insert({1,n,0,1});for(int i1;im;i) {char ss[10];scanf(%s,ss1);if(ss[1]C) {int l,r,c; scanf(%d%d%d,l,r,c);add(l,r,c,i);} else if(ss[1]A) {int c,x; scanf(%d%d,c,x);if(v[c].size()) {LL edv[c].back().x;v[c].pb({xed,i});}else v[c].pb({x,i});} else if(ss[1]Q) {int x; scanf(%d,x);printf(%lld\n,bit.sum(x)query(x));}}
}int main() {int _1;while(_--) {solve();}return 0;
}
