免费检测网站seo,杭州论坛网站建设,泰安小程序网络公司,chatgpt 网址J. Jewel Grab
Tartarus _Wallace_ 转化询问#xff1a;对于一个询问 [s,k]#xff0c;找到一个最长的区间 [s,t]#xff0c;满足区间中出现次数超过一次的元素#xff0c;的出现次数减一#xff0c;的和#xff0c;不超过 k。
对于该区间[s,t] 区间数颜色#xff1a;…J. Jewel Grab
Tartarus _Wallace_ 转化询问对于一个询问 [s,k]找到一个最长的区间 [s,t]满足区间中出现次数超过一次的元素的出现次数减一的和不超过 k。
对于该区间[s,t] 区间数颜色也就是每种颜色只算一个权值求最大和显然每种颜色都取最大的权值于是有下面转化对于所有区间中出现次数超过一次的元素找出其中权值最大的求和对其他的元素仅仅出现一次直接求和。计算最终结果。 区间数颜色显然要维护一个pre[x]数组表示前一个出现c[x]的位置在哪
首先我们考虑如何找到区间的端点t也就是找到[s,t]这个区间。由于k非常小考虑一次只忽略一个宝石也就是每次找到第一个 pre[x]s 的 x 即可那么由于pre[x]和x都在所考虑区间内部于是就需要多一次忽略。
显然c[x]就是出现次数超过一次的元素 于是只需要记录mc[c[x]]每次选择最大的。而对于[cur,x)这段区间都是其他的元素仅仅出现一次直接区间求和即可计算贡献。 考虑如何修改
每当修改一个位置的颜色最多会有3个位置的pre[]发生改变
该位置pre一定改变原颜色后面位置的pre可能改变新颜色后面位置的pre可能改变
可以考虑用一个双链表pre[],nxt[]维护一下。详细参考代码代码都是抄第一篇博客的。
#includebits/stdc.h
using namespace std;
using lllong long;
template class Tint T rd()
{T res0;T fg1;char chgetchar();while(!isdigit(ch)) {if(ch-) fg-1;chgetchar();}while( isdigit(ch)) res(res1)(res3)(ch^48),chgetchar();return res*fg;
}
const int N200010;int n,m;
int pre[N],last[N],nxt[N];
int c[N];ll v[N],mc[N];
setint cp[N];
void prework()
{memset(last,-1,sizeof last);for(int in;i1;i--){nxt[i]last[c[i]];last[c[i]]i;}memset(last,-1,sizeof last);for(int i1;in;i) {pre[i]last[c[i]];last[c[i]]i;cp[c[i]].insert(i);}
}
struct node
{int l,r;int v;ll s;
}t[N2];
void pushup(int u)
{t[u].vmax(t[u1].v,t[u1|1].v);t[u].st[u1].st[u1|1].s;
}
void build(int u,int l,int r)
{t[u]{l,r};if(lr){t[u].vpre[l];t[u].sv[l];return;}int midlr1;build(u1,l,mid),build(u1|1,mid1,r);pushup(u);
}
void modify(int u,int p)
{if(t[u].lt[u].r) {t[u].vpre[p];t[u].sv[p];return;}int midt[u].lt[u].r1;if(pmid) modify(u1,p);else modify(u1|1,p);pushup(u);
}
ll query(int u,int l,int r)
{if(lt[u].lt[u].rr) return t[u].s;int midt[u].lt[u].r1;ll v0;if(lmid) vquery(u1,l,r);if(rmid) vquery(u1|1,l,r);return v;
}
int find(int u,int s,int p)
{if(t[u].lt[u].r) return t[u].l;int midt[u].lt[u].r1;int pos-1;if(t[u1].vspmid) posfind(u1,s,p);if(pos!-1) return pos;if(t[u1|1].vs)posfind(u1|1,s,p);return pos;
}
int main()
{nrd(),mrd();for(int i1;in;i) c[i]rd(),v[i]rd();prework();build(1,1,n);while(m--){int oprd();if(op1){int xrd(),c0rd(),v0rd();cp[c[x]].erase(x);// 最后一次出现的c[x]的位置if(last[c[x]]x) last[c[x]]pre[x];v[x]v0;c[x]c0;// 删除的修改// 链表的一些删除操作if(nxt[x]!-1) {if(pre[x]!-1) {nxt[pre[x]]nxt[x];pre[nxt[x]]pre[x];modify(1,nxt[x]);// nxt[x]的pre[]发生改变需要维护}else{pre[nxt[x]]-1;modify(1,nxt[x]);}}else{if(pre[x]!-1) nxt[pre[x]]-1;}// 插入的修改int pos;setint::iterator it;itcp[c0].lower_bound(x);// 插入在末尾if(itcp[c0].end()){nxt[x]-1;pre[x]last[c0];if(pre[x]!-1) nxt[pre[x]]x;modify(1,x);}else{pos*it;if(pre[pos]!-1) //插入不在开头{nxt[pre[pos]]x;pre[x]pre[pos];modify(1,x);}// 插入在开头else{pre[x]-1;modify(1,x);}nxt[x]pos;pre[pos]x;modify(1,pos);}cp[c0].insert(x);last[c0]max(last[c0],x);}else{int srd(),krd();vectorint col;int curs;ll ans0;for(int j0;jkcurn;j){int posfind(1,s,cur);if(pos-1) {ansquery(1,cur,n);break;}col.push_back(c[pos]);if(jk){// 出现一次直接选if(mc[c[pos]]0) mc[c[pos]]v[pre[pos]];// 出现第二次考虑与第一次出现的比较if(v[pos]mc[c[pos]]){ans-mc[c[pos]];ansv[pos];mc[c[pos]]v[pos];}}ansquery(1,cur,pos-1);// [cur,pos-1]都是第一次出现curpos1;}printf(%lld\n,ans);for(int u:col) mc[u]0;}}return 0;
}太难了吧。。 要加油哦~
