电商网站开发平台实验,最新的新开传奇网站,logo设计大全,佛山网站制作维护P8441 旭日东升 维护一个不可重集合的序列 \(a\)#xff0c;长度为 \(n\)。支持以下两种操作#xff1a; l r x 对于每个 \(l\le i\le r\)#xff0c;将 \(x\) 并入 \(a_i\)。l r 设 \(S\) 把每个 \(l\le i\le r\) 的 \(a_i\) 并在一起的集合#xff0c;输出 \(S\) 中所有元… P8441 旭日东升 维护一个不可重集合的序列 \(a\)长度为 \(n\)。支持以下两种操作 l r x 对于每个 \(l\le i\le r\)将 \(x\) 并入 \(a_i\)。l r 设 \(S\) 把每个 \(l\le i\le r\) 的 \(a_i\) 并在一起的集合输出 \(S\) 中所有元素的和。 \(n,m,x\le 10^5,1\le l\le r\le n\)。 \(\color{yellow}{\bigstar\texttt{Trick}}\)连续的不可重集合 \(\rightarrow\) 含有每种颜色的地方以不重叠的区间形式存在考虑用 ODT 维护区间中是否有这个数。如果我们能在每次操作之后都将 \([1,n]\) 的区间划分不存在连续的 \(0\) 区间的若干段那么不含有这个数的区间一定是被完全包含在 \(0\) 区间中。 为了实现对区间端点的限制两位神仙为我们指引了方向 \(\texttt{p}\color{red}{\texttt{igstd}}\)这个问题可以转化为矩形加、单点求值之后想方法实现。 \(\texttt{B}\color{red}{\texttt{uttercake}}\)矩形加、单点求值可以将询问和修改离线按照左端点排序将操作存储在左端点并用树状数组维护但常数很小。(update即将矩形差分后离线处理) 于是你就做完了 此题代码 #define Maxn 100005
int n,m;
ll ans[Maxn];
struct BIT
{ll tree[Maxn];inline void add(int x,ll k){ while(xn) tree[x]k,xx(-x); }inline ll query(int x){ ll ret0; while(x) rettree[x],x-x(-x); return ret; }
}T;
struct ODT
{int l,r,val;ODT(int L0,int R0,int Val0):l(L),r(R),val(Val){}bool friend operator (ODT x,ODT y) { return x.ly.l; }
};
setODT s[Maxn];
struct Operation
{int opt,l,r,val,num;Operation(int Opt0,int L0,int R0,int Val0,int Num0):opt(Opt),l(L),r(R),val(Val),num(Num){}bool friend operator (Operation x,Operation y) { return x.ly.l; }
};
vectorOperation op;
inline void add(int l,int r,int val)
{op.emplace_back(0,l,l,val,0);op.emplace_back(0,l,r1,-val,0);op.emplace_back(0,r1,l,-val,0);op.emplace_back(0,r1,r1,val,0);
}
inline auto split(int opt,int x)
{if(!s[opt].size()) s[opt].emplace(1,n1,0);auto its[opt].lower_bound(ODT(x,0,0));if(it!s[opt].end() it-lx) return it;it--;int lit-l,rit-r,valit-val;if(it-val0) add(l,r,opt),add(l,x-1,-opt),add(x,r,-opt);s[opt].erase(it);s[opt].emplace(l,x-1,val);return s[opt].emplace(x,r,val).fi;
}
inline void assign(int opt,int l,int r)
{if(!s[opt].size()) s[opt].emplace(1,n1,0);auto itrsplit(opt,r1),itlsplit(opt,l);for(auto ititl;it!itr;it)if(it-val0) add(it-l,it-r,opt);s[opt].erase(itl,itr);s[opt].emplace(l,r,1);
}
void solve(int ql,int qr)
{if(qlqr) return;int mid(qlqr)1;solve(ql,mid),solve(mid1,qr);int nlql;for(int nrmid1;nrqr;nr) if(op[nr].opt){while(nlmid op[nl].lop[nr].l){ if(op[nl].opt0) T.add(op[nl].r,op[nl].val); nl; }ans[op[nr].num]T.query(op[nr].r);}for(int iql;inl;i) if(op[i].opt0) T.add(op[i].r,-op[i].val);inplace_merge(op.begin()ql,op.begin()mid1,op.begin()qr1);
}
int main()
{nrd(),mrd();for(int i1,opt,l,r,x;im;i){optrd(),lrd(),rrd();if(opt1) xrd(),assign(x,l,r),ans[i]-1;else op.emplace_back(1,l,r,0,i),ans[i]0;}solve(0,op.size()-1);for(int i1;im;i) if(ans[i]!-1) printf(%lld\n,ans[i]);return 0;
} 于是你已经对二维数点的基本原理有了一定的了解就让我们来看一看下面这个简单的例子来吧我们刚刚学到的知识运用到时间中吧。 试试看(bushi CF848C Goodbye Souvenir 修改一个元素其实就是删除一个元素后增加一个元素分别考虑他们的贡献是多好 设当前下标为 \(x\)上一个这种元素为 \(p\)下一个元素为 \(s\)则 加入一个元素 \(l\in[1,p],r\in[x,s)\) 区间加上 \(x-p\)。\(l\in(p,x],r\in[s,n]\) 区间加上 \(s-x\)。 删除一个元素将加法的权值倒过来即可。 我们需要查询的是区间和即变为了一个矩形加、单点查询问题离线解决即可。 P4690 [Ynoi2016] 镜中的昆虫 维护一个长为 \(n\) 的序列 \(a_i\)有 \(m\) 次操作。 1 l r x 将区间 \([l,r]\) 的值修改为 \(x\)。2 l r 询问区间 \([l,r]\) 出现了多少种不同的数也就是说同一个数出现多次只算一个。 \(1\le n,m\le 10^5,1\le a_i\le 10^9\)。 和上一题不能说差不多只能说十分相似(bushi 用一个 ODT 维护全局颜色端对每个颜色再分别维护颜色端。 用矩形加、单点查的套路做分治解决即可。
