10.14模擬賽
t1：
Alice 正在玩一個 multiset。最初，集合中只有一個元素 \(0\)。每一輪，集合中的每一個元素 \(x\) 都有 \(3\) 種可能的操作：
-
1.\(x\) 加上 \(1\)，即 \(x = x +1\)。
-
2.\(x\) 分裂成兩個非負整數 \(y\)，\(z\)。即 \(x = y + z\)，且 \(y \ge0\)，\(z \ge 0\)。
-
3.什么都不做。
注意，在一輪中每個元素只能選擇一種操作。
Alice 已經玩了很久了，但她并不知道自己已經玩了多少輪?，F在給出最終的集合，請你輸出 Alice 最少玩的輪數。
對于 \(100\%\) 的數據：$ N \le 1,000,000$, $A_i \le 1,000,000 $。
題解：
容易想到貪心。因為先分裂比增加后再分裂更優。但何時邊分裂邊增加呢？何時只分裂不增加呢？
顯然正序模擬不可行，考慮倒序模擬。
對于當前狀態中的 \(0\) 元素將他們兩兩合并（\(0\) 元素只能被快速分裂得到），對于當前狀態中的所有非 \(0\) 元素將他們共同 \(-1\)。
當然我們也可以正序套上二分來解決。
t2：
不同于我們所在的世界, 在顏神的世界里, 時間線并不是一條直線, 而是一個環。設時間線連成的環 的長度為 \(L\), 當顏神順著時間線前進時, 若跨過了第 \(L\) 個時刻, 就會回到第 \(0\) 個時刻。反過來, 若逆著 時間線前進, 且跨過了第 $0 $ 個時刻, 則會回到第 \(L\) 個時刻。在整個時間環上有 \(n\) 個顏神, 每個顏神都是 順著時間線或逆著時間線以相同的速度前進。若同一時刻沿著不同方向行走的兩個顏神相遇, 則會產生 正反物質湮滅, 導致無法預料的災難。因此若兩個顏神同時位于某一個時刻 (可能是小數時刻), 則他們 會在該時刻同時進入反轉機來改變自己的運動方向。
現在給定每個顏神所在的位置以及運動方向, 請告訴管理時空的至高之神 beginend, \(T\) 個時刻以后, 每個顏神在時間環中所在的位置。
對于 \(100 \%\) 的數據, \(1 \leq n \leq 10^{5}, 1 \leq L, T \leq 10^{9}, 0 \leq X_{1}<X_{2}<\cdots<X_{n} \leq L-1,1 \leq W_{i} \leq 2\) 。
題解：
考慮所有顏神相對位置都不變，而且換方向等同于替換編號，考慮先直接求除每個點不換方向的答案。那么我們只用知道其中一個點具體是哪個點就好了。
所以先求出所有顏神最終所在的位置集合。初始狀態坐標最小的顏神編號為 \(1\) 。在行走過程中, 若有一 個顏神從 \(0\) 走到 \(L-1\), 那么坐標最小的顏神的編號就會加 \(1\) 。若有一個顏神從 \(L-1\) 走到 \(0\), 坐標最 小的顏神的編號就會減 1 。這樣就可以得到最終位置的坐標最小的是哪一個顏神了。
t3：
由于阿巴阿巴的原因，你需要給歪比歪比的一張圖進行定向
記這張無向圖為 \(G\)，無自環，但可能有重邊
每條邊的邊權為 \(1,3,5\) 中的一種
設 \(deg(x)=\sum_{(u,v)\in E}[[u=x]\cup [v=x]]\)，滿足 \(\forall x\in V,2|deg(x)\)
\(\cup\) 表示或者, \([~]\) 表示條件判斷，括號內為真返回值為 \(1\)，否則為 \(0\)
現在你需要給每沒邊定向,即對于任意一條無向邊 \((u,v)\)，設為 \(u\to v\) 或者 \(v\to u\) 的有向邊
現在設 \((u,v)\) 表示一個 \(u\to v\) 的邊，\(w(u,v)\) 表示此邊的邊權
\(\forall x\in V\)，設 \(S1=\sum_{(u,v)\in E\cap u=x}w(u,v),S2=sum_{(u,v)\in E\cap v=x}w(u,v)\)，滿足 \(|S1-S2|\leqslant 4\)
\(\cap\) 表示集合并。
可能存在多種定向方式,輸出任意一種即可；如果不存在定向方式，輸出一行一個 \(-1\)
注: \(V=\left \{1,2,3,...,n\right \}\)
題解：
令\(D(u)=S1-S2\)，同時我們準備一張新圖\(G'(V,\emptyset)\)
首先對每種邊權分別處理
設當前處理的是w，那么把邊權為w的邊拿出來，組成新圖\(G_w\left \{V,E_w\right \}\)
deg(u)表示u的度數
首先我們給\(G_w\)新填一個虛點y，然后我們給\(G_w\)加一些邊
如果\(deg(u)\equiv 1(mod\ 2)\)，則連\(y-u\)(無向邊)
然后我們可以對\(G_w\)的每個聯通塊跑一個歐拉回路
若聯通塊里面沒有y,直接按回路的方向定向(對于A性質,y沒有添加的必要，于是就解決了)
對于y所在的聯通塊，令這個回路從y出發，然后最后回到y
把y在這個回路中的位置標出來，形如
\(y-a_1-....-b_1-y-a_2-...-b_2-y-...-y-a_l-...-b_l-y\)
冷靜分析
- \(a_i,b_i\)互不相同
- \(\forall_{1\leqslant i\leqslant l},deg(a_i)\equiv deg(b_i)\equiv 1(mod \ 2)\)
- 對于$u\in y $ 所在的聯通塊 $ \ deg(u)\equiv 1(mod\ 2)$,u在a或b中出現恰好一次
按照D的定義，截取\(a_i-...-b_i\)這一段路徑，實際上執行了\(D(a_i)+=w\)和\(D(b_i)-=w\) 的操作，把路徑上的邊翻轉，就執行了\(D(a_i)-=w\)和\(D(b_i)+=w\)
我們對G'添加邊\((a_i,b_i,w)\)
對\(w\in\left\{1,3,5\right\}\)都執行上面的操作
現在我們只要對G‘定向滿足條件就好了
因為保證了G中\(deg(u)\equiv 0(mod\ 2)\)
所以G'滿足B性質
觀察G'中的聯通塊，要么是單點，要么是一個環，環的定向用順時針方向或者逆時針方向均可
#include<bits/stdc++.h>
using namespace std;
#define cout cerr
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef pair<int,int> pii;
#define FR first
#define SE second
namespace IO{
char buf[1000010],*cur=buf+1000010;
inline char getc(){
(cur==buf+1000010)?fread(cur=buf,1,1000010,stdin):0;
return *cur++;
}
char buff[1000010],*curr=buff;
inline void flush(){
fwrite(buff,1,curr-buff,stdout);
}
inline void putc(const char &ch){
(curr==buff+1000010)?fwrite(curr=buff,1,1000010,stdout):0;
*curr++=ch;
}
inline void rd(int &x){
x=0;char ch=getc();int f=1;
while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;
ch=getc();
}
while(ch>='0'&&ch<='9'){
x=x*10+ch-'0';
ch=getc();
}
x*=f;
}
char st[60];int tp;
void PT(int x){
if(x==0)putc('0');
else{
while(x>0){
st[++tp]=x%10+'0';
x/=10;
}
}
while(tp)putc(st[tp--]);
}
}
using IO::getc;
using IO::putc;
using IO::rd;
using IO::PT;
int n,m;
#define V 1500010
#define E 3000010
int stk[E],top,U[E],len;
bool c[E<<1];
int rev(int x){
if(x&1)return x+1;
return x-1;
}
namespace sub{
int head[V],v[E],nxt[E],tot=0;
inline void add_edge(int s,int e){
tot++;v[tot]=e;nxt[tot]=head[s];head[s]=tot;
tot++;v[tot]=s;nxt[tot]=head[e];head[e]=tot;
}
int p[V],cnt;
bool vis[V];
void Euler(int u){
while(head[u]){
int t=head[u];head[u]=nxt[head[u]];
if(!vis[(t+1)/2]){
vis[(t+1)/2]=true;
Euler(v[t]);
p[++cnt]=t;
}
}
}
void solve(){
rep(u,1,n){
cnt=0;Euler(u);
rep(i,1,cnt){
int t=(p[i]+1)/2;
if(p[i]&1)
rep(j,U[t-1]+1,U[t])c[stk[j]]=true;
else
rep(j,U[t-1]+1,U[t])c[rev(stk[j])]=true;
}
}
}
}
struct Edge{
int s,e;
}edge[E];
vector<int> vec[3];
int head[V],v[E*3],nxt[E*3],tot=0;
bool deg[V];
bool vis[V*3];
inline void add_edge(int s,int e){
deg[s]^=1;deg[e]^=1;
tot++;v[tot]=e;nxt[tot]=head[s];head[s]=tot;
tot++;v[tot]=s;nxt[tot]=head[e];head[e]=tot;
}
int p[V*3],cnt;
void Euler(int u){
while(head[u]){
int t=head[u];head[u]=nxt[head[u]];
if(!vis[(t+1)/2]){
vis[(t+1)/2]=true;
Euler(v[t]);
p[++cnt]=t;
}
}
}
void calc(vector<int> &g){
tot=0;memset(head,0,sizeof(int)*(n+2));memset(deg,0,sizeof(bool)*(n+2));
for(int i=0;i<g.size();++i){
int id=g[i];
add_edge(edge[id].s,edge[id].e);
}
int pre=tot;
rep(i,1,n)
if(deg[i])add_edge(n+1,i);
memset(vis,false,sizeof(bool)*(tot/2+1));
cnt=0;Euler(n+1);
reverse(p+1,p+cnt+1);
for(int i=1,lst;i<=cnt;i=lst+1)
if(p[i]>pre){
lst=i+1;
while(p[lst]<=pre){
int t=p[lst],id=g[(t+1)/2-1];
stk[++top]=id*2-(t&1);
lst++;
}
U[++len]=top;
sub::add_edge(v[p[i]],v[rev(p[lst])]);
}
rep(u,1,n){
cnt=0;Euler(u);
if(cnt){
rep(i,1,cnt){
int t=p[i],id=g[(t+1)/2-1];
c[2*id-(t&1)]=true;
}
}
}
}
int main(){
freopen("graph.in","r",stdin);freopen("graph.out","w",stdout);
rd(n);rd(m);
int s,e,t;
rep(i,1,m){
rd(edge[i].s);rd(edge[i].e);rd(t);
vec[t/2].push_back(i);
}
rep(i,0,2)calc(vec[i]);
sub::solve();
rep(i,1,m)
if(c[2*i-1])putc('0');
else putc('1');
IO::flush();
return 0;
}
t4：
你得到了一個長度為 \(\mathrm{n}\) 的數列 \(A\), 要求支持以下 2 種操作: 第一種是給 定 \(L, R, X\)，要求把區間中比 \(X\) 小的數字全部修改為 \(X\) 第二種是給定 \(L, R, K, X\) 查詢區間中比 \(\mathrm{X}\) 小的最小的 \(\mathrm{K}\) 個數，并且將它們升序輸出，沒有則輸出 \(-1\)。
對于全部數據, 滿足 \(1<=\mathrm{n}, \mathrm{m}<=500000,1<=\mathrm{L}<=\mathrm{R}<=\mathrm{n}, 1<=\mathrm{K}<=\mathrm{n}, 1<=\mathrm{A_i}, \mathrm{X}<=10^9\), 對于所有 操作 2 中的 \(\mathrm{K}, \mathrm{K}\) 的總和不超過 \(5 \times 10^6\) 。
題解：
Tag: 線段樹, 堆
小調查: 有多少選手現場學習并實現了 segment tree beats 呢?
\(\# 1: n, m<=3000\), 直接模擬, 考察選手對 std: : sort 的使用
\(\# 2\) : RMQ 問題, 可以通過 ST 表或者線段樹實現, 注意 -1 的判斷
# 3：區間把比一個數小的數字變成這個數, 查詢區間最小值.
因為查詢內容與區間和值等無關, 所以無需 Segment Tree Beats 中的方法實現,
直接在每個線段樹節點上維護當前區間 min 值以及區間與哪個數取 max 的 lazy 標記即
可
# 4: 考慮操作 2 怎么解決, 因為 \(\mathrm{K}\) 的和值不超過 \(5 * 10^{\wedge} 6\), 考慮與其相關的做法.
對序列建一棵線段樹, 線段樹上每個節點維護當前區間最小值的值和位置, 同時用一個 小根堆去維護最后的答案, 線段樹上每次 query \((1, r)\) 返回一組 \(\{v a 1, p o s, 1, r\}\) 表示 \([1, r]\) 區 間中最小值為 val, 位置為 pos, 按照 val 去建立這個小根堆.
開始把 query \((1, n)\) 的結果入堆, 然后重復 \(K\) 次以下操作:
每次彈出堆頂, 顯然這時的 \(val\) 是所剩下的數中的最小值,
然后將 \(query ( 1 , pos -1)\) 以及 \(query (pos +1, r)\) 的結果入堆,
這樣得到的 \(K\) 個堆頂顯然是最小的 \(K\) 個元素, 判斷 \(-1\) 后輸出即可,
而關于時間復雜度, \(query\) 與入堆的次數都是 \(2 \mathrm{~K}\) 次, 彈出的次數為 \(\mathrm{K}\) 次,
所以總復雜度為 \(0(n+\operatorname{sigma}(K) * \log n)\).
\(\# 5, \# 6\) : 發現在# 4 與 \(\# 3\) 的維護區間 \(\min\) 值并不會產生影響, 于是將 \(\# 3\), # 4一起實現, 即 可通過全部數據, 時間復雜度 \(0((n+\operatorname{sigma}(K)) * \log n)\), 空間復雜度 \(0(n+\operatorname{sigma}(K))\).
對于 \(1<=n, m<=100000\) 的另解:
如果你想不到堆+線段樹維護的方法, 可以利用下發課件中開篇提到的平衡樹套支持區 間取 max 的線段樹做到 \(0((\mathrm{n}+\mathrm{m}) \log^3 \mathrm{n})\), 也可以用分塊做到 \(O (n\sqrt n\log n)\), 均可通過 滿足 \(1<=n, m<=100000\) 的數據得到高分.
#include<bits/stdc++.h>
#define ls (p<<1)
#define rs (p<<1|1)
#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int N=5e5+10;
int n,m,k,T,a[N],laz[N<<2],ans[N],cnt;
vector<int> g[N];
struct tree{
int mi,pos;
}t[N<<2];
void pushup(int p){
if(t[ls].mi<=t[rs].mi) t[p]=t[ls];
else t[p]=t[rs];
}
struct node{
int x,pos,l,r;
friend bool operator<(node a,node b){
return a.x>b.x;
}
};priority_queue<node> q;
void pushdown(int p){
if(laz[p]==0) return;
int k=laz[p];laz[p]=0;
laz[ls]=max(k,laz[ls]);
laz[rs]=max(laz[rs],k);
if(t[ls].mi<laz[ls]) t[ls]={laz[ls],t[ls].pos};
if(t[rs].mi<laz[rs]) t[rs]={laz[rs],t[rs].pos};
}
void build(int p,int l,int r){
if(l==r){
t[p]={a[l],l};return;
}int mid=l+r>>1;
build(ls,l,mid);build(rs,mid+1,r);
pushup(p);
}
void upd(int p,int l,int r,int x,int y,int k){
if(x<=l&&r<=y){
laz[p]=max(laz[p],k);
if(t[p].mi<k) t[p]={k,t[p].pos};
return;
}int mid=l+r>>1;pushdown(p);
if(x<=mid) upd(ls,l,mid,x,y,k);
if(y>mid) upd(rs,mid+1,r,x,y,k);
pushup(p);
}
tree query(int p,int l,int r,int x,int y){
if(x<=l&&r<=y){
return t[p];
}int mid=l+r>>1;pushdown(p);
if(y<=mid) return query(ls,l,mid,x,y);
else if(x>mid) return query(rs,mid+1,r,x,y);
else{
tree res1=query(ls,l,mid,x,y);
tree res2=query(rs,mid+1,r,x,y);
if(res1.mi<=res2.mi) return res1;
else return res2;
}
}
void solve(int l,int r,int x,int k){
tree res=query(1,1,n,l,r);
cnt=0;q.push({res.mi,res.pos,l,r});
while(k--){
node t=q.top();q.pop();
if(t.x>=x){cnt=-1;return;}
ans[++cnt]=t.x;
if(t.l!=t.pos){
tree res1=query(1,1,n,t.l,t.pos-1);q.push({res1.mi,res1.pos,t.l,t.pos-1});
}if(t.r!=t.pos){
tree res2=query(1,1,n,t.pos+1,t.r);q.push({res2.mi,res2.pos,t.pos+1,t.r});
}
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
freopen("segtree.in","r",stdin);
freopen("segtree.out","w",stdout);
cin>>n;
rep(i,1,n) cin>>a[i];
build(1,1,n);
cin>>m;
while(m--){
int op;cin>>op;
if(op==1){
int l,r,x;cin>>l>>r>>x;
upd(1,1,n,l,r,x);
}else{
while(!q.empty()) q.pop();
int l,r,x,k;cin>>l>>r>>x>>k;
solve(l,r,x,k);
if(cnt==-1) cout<<-1;
else rep(i,1,cnt) cout<<ans[i]<<" ";
cout<<'\n';
}
}
return 0;
}
浙公網安備 33010602011771號