AtCoder 五十连练 第二练
D - Union of Interval
给定 \(N\) 个左闭右开的区间，求这些区间的并集。
数据范围：\(1 \le N \le 2 \times 10^5\)。
Code.
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int st[N],n,cnt,mx;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
int l,r; scanf("%d%d",&l,&r); mx=max(mx,r);
st[l]++; st[r]--;
}
for(int i=1;i<=mx;i++)
{
if(cnt == 0 && st[i]) cout<<i<<" ";
if(st[i] < 0 && cnt+st[i] == 0) cout<<i<<endl;
cnt+=st[i];
}
return 0;
}
E - Takahashi's Anguish
一共有 \(N\) 个人，编号从 \(1\) 到 \(N\)。
高桥决定选择一个序列 \(P=(P_1,P_2,...,P_N)\)，这是一个从 \(1\) 到 \(N\) 的整数的排列，并按照这个顺序给 \(P_1,P_2,...,P_N\) 人一个糖果。
由于第 \(i\) 号人不喜欢第 \(X_i\) 号人，如果高桥先给第 \(X_i\) 号人糖果，那么第 \(i\) 号人会有 \(C_i\) 的挫折感；否则，第 \(i\) 号人的挫败感为 \(0\)。
高桥可选择任意序列 \(P\)，使他们的挫折感的最小可能总和是多少?
数据范围：\(2 \le N \le 2 \times 10^5,1 \le C_i \le 10^9\)。
我们可以从人 \(i\) 向他讨厌的第 \(X_i\) 号人连边，发现图构成了一颗基环树，显然产生矛盾的情况为他们在一个环上，链不会对答案造成贡献，我们需要破环成链，考虑一步贪心，我们可以选择环上最小的那个点将他计入贡献，有向边，所以是强连通分量所有大于 \(1\) 的分量中最小那个点计入答案， \(tarjan\) 缩点即可，注意开 long long，时间复杂度 \(O(n+m)\) ，要我说可以把数据规模拉到 \(10^6\)，时限开小一点，把那些非正解暴力 \(O(n \log n)\) 的并查集全部干碎。
Code.
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int n,h[N],ne[N<<1],e[N<<1],idx,w[N],sz[N],mn[N],scc_cnt,stk[N],top,dfn[N],low[N],in_stk[N],nowstep,res;
void add(int u,int v) {ne[++idx]=h[u],e[idx]=v,h[u]=idx;}
void tarjan(int u)
{
dfn[u]=low[u]=++nowstep; stk[++top]=u; in_stk[u]=1;
for(int i=h[u];~i;i=ne[i])
{
int j=e[i];
if(! dfn[j]) {tarjan(j); low[u]=min(low[u],low[j]);}
else if(in_stk[j]) low[u]=min(low[u],dfn[j]);
}
if(low[u] == dfn[u])
{
++scc_cnt; int y;
do
{
y=stk[top--]; in_stk[y]=0;
mn[scc_cnt]=min(mn[scc_cnt],w[y]);
sz[scc_cnt]++;
} while(y != u);
}
}
signed main()
{
memset(h,-1,sizeof h); memset(mn,0x7f,sizeof mn);
scanf("%lld",&n);
for(int i=1,x;i<=n;i++) {scanf("%lld",&x); add(i,x);}
for(int i=1;i<=n;i++) scanf("%lld",w+i);
for(int i=1;i<=n;i++) if(! dfn[i]) tarjan(i);
for(int i=1;i<=scc_cnt;i++) {if(sz[i] == 1) continue ; res+=mn[i];}
printf("%lld\n",res);
return 0;
}
F - Cumulative Cumulative Cumulative Sum
atcoder 的题是不是对取模有特别的执着？
写一个数据结构，支持单点修改，查询原数列的前缀和的前缀和的前缀和，对 \(998244353\) 取模。
数据范围：\(1 \le N \le 2 \times 10^5\)。
\(\begin{aligned} d_{i} &=(1+2+\cdots+i) a_{1}+(1+2+\cdots+(i-1)) a_{2}+\cdots+a_{i} \\ &=\sum_{j=1}^{i} \frac{(i-j+1)(i-j+2)}{2} a_{j} \\ &=\frac{1}{2}\left(\sum_{j=1}^{i} j^{2} a_{j}-(2 i+3) \sum_{j=1}^{i} j a_{j}+(i+1)(i+2) \sum_{j=1}^{i} a_{j}\right) \end{aligned}\)
我们只需要开三个树状数组同时维护 \(a_i,a_i \times i,a_i \times i^2\) 就可以了，对了，还有一个 \(2\) 的逆元。
Code.
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10,mod=998244353;
int n,q,inv=499122177,a[N],t1[N],t2[N],t3[N];
int lowbit(int x) {return x&-x;}
void modify(int *tr,int x,int k) {if(x <= 0) return ; for(int i=x;i<N;i+=lowbit(i)) tr[i]=(tr[i]+k)%mod;}
int query(int tr[],int x) {int res=0; for(int i=x;i;i-=lowbit(i)) res=1ll*(res+tr[i])%mod; return res%mod;}
void add(int x,int y) {modify(t1,x,y); modify(t2,x,x*y%mod); modify(t3,x,x*x%mod*y%mod);}
signed main()
{
scanf("%lld%lld",&n,&q);
for(int i=1;i<=n;i++) scanf("%lld",a+i),add(i,a[i]);
while(q -- )
{
int op,x,v; scanf("%lld",&op);
if(op == 1)
{
scanf("%lld%lld",&x,&v);
add(x,-a[x]); a[x]=v; add(x,a[x]);
}
else
{
scanf("%lld",&x); int res=(x+1)*(x+2)%mod*query(t1,x)%mod;
res=(res-(2*x+3)%mod*query(t2,x)%mod+mod)%mod; res=(res+query(t3,x))%mod; res=res*inv%mod;
printf("%lld\n",(res+mod)%mod);
}
}
}
G - Black and White Stones
矩阵快速幂优化 dp ，好题，不想写了。挖个坑回来补。
Ex - I like Query Problem
好题，让你写个数据结构，同时支持区间推平，区间整除，查询区间和，这是个裸的势能线段树，但我珂朵莉树上头，写了个珂朵莉树套线段树维护，具体思路在 luogu 的这个 讨论 里了，复杂度应该是正确的吧，这个操作可以叫珂朵莉树二次在线吧。
理论上就是珂朵莉树用来维护区间权值相等的极大块，再写一颗有区间推平的线段树辅助查询，均摊复杂度应该在两只 \(\log\) 左右，常数大，作为有 区间推平 操作的势能线段树的下位替代品，可以说是用珂朵莉树来简化修改，或者说是用线段树来优化查询了？
优点可能是少去了原本在线段树上分析势能的操作，比较无脑且好写吧。比较好玩，回来可以单独发篇博客？
数据范围：\(1 \le N \le 5 \times 10^5\)。
Code.
#include<bits/stdc++.h>
#define int long long
inline char gc()
{
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
#define gc getchar
inline int read()
{
int x=0; char c=gc(); bool f=0;
for(;c<'0'||c>'9';c=gc()) f|=(c=='-');
for(;c>='0'&&c<='9';c=gc()) x=(x<<1)+(x<<3)+(c^48);
return x=f ? -x : x;
}
using namespace std;
const int N=5e5+10;
int n,q,a[N],tt; struct Seg {int l,r,sum,tag;} tr[N<<2];
inline void pushup(int u) {tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;}
inline void pushdown(int u)
{
if(tr[u].tag != -1)
{
tr[u<<1].sum=tr[u].tag*(tr[u<<1].r - tr[u<<1].l + 1);
tr[u<<1|1].sum=tr[u].tag*(tr[u<<1|1].r - tr[u<<1|1].l + 1);
tr[u<<1].tag=tr[u<<1|1].tag=tr[u].tag;
}
tr[u].tag=-1;
}
inline void build(int u,int l,int r)
{
tr[u].l=l,tr[u].r=r,tr[u].tag=-1;
if(l == r) return tr[u].sum=a[l],void();
int mid = (l + r) >> 1ll;
build(u<<1,l,mid); build(u<<1|1,mid+1,r);
pushup(u);
}
inline int query(int u,int l,int r)
{
if(l <= tr[u].l && tr[u].r <= r) return tr[u].sum;
pushdown(u);
int mid = (tr[u].l + tr[u].r) >> 1ll,res=0;
if(l <= mid) res=query(u<<1,l,r); if(mid < r) res+=query(u<<1|1,l,r);
return res;
}
inline void modify(int u,int l,int r,int k)
{
if(l <= tr[u].l && tr[u].r <= r)
{
tr[u].sum=k*(tr[u].r - tr[u].l + 1);
tr[u].tag=k; return ;
}
pushdown(u);
int mid = (tr[u].l + tr[u].r) >> 1ll;
if(l <= mid) modify(u<<1,l,r,k); if(mid < r) modify(u<<1|1,l,r,k);
pushup(u);
}
struct node
{
int l,r; mutable int v;
bool operator < (const node &o) const {
return l < o.l;
}
} t[N]; set<node> s;
inline set<node> :: iterator split(int pos)
{
auto it=s.lower_bound(node{pos,-1,0});
if(it->l == pos && it != s.end()) return it;
it -- ; int l=it->l,r=it->r,v=it->v;
s.erase(it); s.insert(node{l,pos-1,v});
return s.insert(node{pos,r,v}).first;
}
inline void assign(int l,int r,int v)
{
auto itr=split(r+1),itl=split(l);
s.erase(itl,itr); s.insert(node{l,r,v});
modify(1,l,r,v);
}
inline void qr(int l,int r,int x)
{
auto itr=split(r+1),itl=split(l); int pl=0,yl=1;
for(auto it=itl;it!=itr;it++) it->v/=x,t[++pl]=*it;
s.erase(itl,itr);
for(int i=2;i<=pl;i++)
{
if(t[i].v == t[yl].v) t[yl].r=t[i].r;
else t[++yl]=t[i];
}
for(int i=1;i<=yl;i++)
{
s.insert(node{t[i].l,t[i].r,t[i].v});
modify(1,t[i].l,t[i].r,t[i].v);
}
}
signed main()
{
n=read(); q=read();
for(int i=1,l=1;i<=n;i++)
{
a[i]=read(); if(i == 1) tt=a[i];
else if(a[i] != tt || i == n)
{
s.insert(node{l,i-1,tt});
l=i,tt=a[i];
}
}
s.insert(node{n,n,a[n]}); build(1,1,n);
while(q -- )
{
int op=read(),l=read(),r=read();
if(op == 1) qr(l,r,read());
else if(op == 2) assign(l,r,read());
else printf("%lld\n",query(1,l,r));
}
return 0;
}