题解.pdf
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m,k;
struct edge{ll u,v,w;}E[200010];
bool cmp(edge A,edge B){return A.w<B.w;}
ll fa[200010];
ll get(ll x){
if(fa[x] == x) return x;
return fa[x] = get(fa[x]);
}
int main(){
freopen("speed.in", "r", stdin);
freopen("speed.out", "w", stdout);
scanf("%lld%lld%lld",&n,&m,&k);
for(int i=1;i<=m;i++) scanf("%lld%lld%lld",&E[i].u,&E[i].v,&E[i].w);
for(int i=1;i<=n;i++) fa[i]=i;
sort(E+1,E+1+m,cmp);
ll ans1=abs(E[1].w-k);
for(int i=2;i<=m;i++) ans1=min(ans1,abs(E[i].w-k));
ll ans=0;
ll cnt=0;
for(int i=1;i<=m;i++){
ll fu = get(E[i].u);
ll fv = get(E[i].v);
if(fu != fv){
fa[fu] = fv;
if(E[i].w > k) ans+=E[i].w-k;
cnt++;
}
if(cnt==n-1){
if(E[i].w < k) ans=ans1;
break;
}
}
printf("%lld\n",ans);
return 0;
}
#include<bits/stdc++.h>
using namespace std;
inline void work() {
set<pair<int,int> > st;
int mx = 2e9, pos = 2e9, last = -1;
bool ok = true;
int n, m;
cin >> n >> m;
while(m--) {
string op;
int p, q;
cin >> op;
if (op == "min") {
if (!ok) cout << "bad" << endl;
else if (last != -1) {
auto ptr = st.lower_bound({last, 0});
if ((prev(ptr) -> first) == (ptr -> first) - 1) cout << (ptr -> first) << endl;
else cout << (prev(ptr) -> first) + 1 << endl;
} else {
if (st.size() == 0) cout << "0" << endl;
else {
auto ptr = *st.begin();
cout << (ptr.first + ptr.second + 1) % 2 << endl;
}
}
} else if (op == "max") {
if (!ok) cout << "bad" << endl;
else if (mx == 2e9) cout << "inf" << endl;
else cout << mx << endl;
} else {
cin >> p >> q;
if (abs(p - 1) > q) {ok = false; continue;}
if (p > 1) pos = min(pos, q);
if (p > 1) mx = min(mx, q - abs(p - 1));
st.insert({q, p});
auto ptr = st.find({q, p});
if (ptr != st.begin() && next(ptr) != st.end() && last == (next(ptr) -> first)) last = -1;
if (ptr != st.begin()) {
auto pre = *prev(ptr);
if ((pre.first + pre.second) % 2 != (p + q) % 2) last = max(last, q);
if (abs(pre.second - p) > abs(pre.first - q)) {ok = false; continue;}
}
if (next(ptr) != st.end()) {
auto nxt = *next(ptr);
if ((nxt.first + nxt.second) % 2 != (p + q) % 2) last = max(last, nxt.first);
if (abs(nxt.second - p) > abs(nxt.first - q)) {ok = false; continue;}
}
if (last > pos) {ok = false; continue;}
}
}
}
int main() {
freopen("drunkard.in", "r", stdin);
freopen("drunkard.out", "w", stdout);
cin.tie(0);
ios::sync_with_stdio(false);
work();
return 0;
}
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define N 100007
#define ls (rt << 1)
#define rs (rt << 1 | 1)
#define mid ((l + r) / 2)
ll a[N], b[N];
struct SEG1 {
bool tag[N << 2][3];
void build(int rt, int l, int r) {
if (l == r) {
tag[rt][0] = (b[l] == 0);
tag[rt][1] = (b[l] > 0);
tag[rt][2] = (b[l] < 0);
return;
}
build(ls, l, mid);
build(rs, mid + 1, r);
rep(i, 0, 2) tag[rt][i] = tag[ls][i] && tag[rs][i];
}
void upd(int rt, int l, int r, int p) {
if (l == r) {
tag[rt][0] = (b[l] == 0);
tag[rt][1] = (b[l] > 0);
tag[rt][2] = (b[l] < 0);
return;
}
p <= mid ? upd(ls, l, mid, p) : upd(rs, mid + 1, r, p);
rep(i, 0, 2) tag[rt][i] = tag[ls][i] && tag[rs][i];
}
bool query(int rt, int l, int r, int L, int R, int op) {
if (L <= l && r <= R) return tag[rt][op];
bool ret = true;
if (L <= mid) ret = ret && query(ls, l, mid, L, R, op);
if (R > mid) ret = ret && query(rs, mid + 1, r, L, R, op);
return ret;
}
} seg1;
pair<ll, int> max(pair<ll, int> a, pair<ll, int> b) {
if (a.first > b.first) return a;
return b;
}
struct SEG2 {
int mxpos[N << 2];
ll mx[N << 2], tag[N << 2];
void pushdown(int rt) {
if (tag[rt]) {
mx[ls] += tag[rt];
mx[rs] += tag[rt];
tag[ls] += tag[rt];
tag[rs] += tag[rt];
tag[rt] = 0;
}
}
void pushup(int rt) {
if (mx[ls] > mx[rs]) {
mx[rt] = mx[ls];
mxpos[rt] = mxpos[ls];
} else {
mx[rt] = mx[rs];
mxpos[rt] = mxpos[rs];
}
}
void build(int rt, int l, int r) {
tag[rt] = 0;
if (l == r) {
mx[rt] = a[l];
mxpos[rt] = l;
return;
}
build(ls, l, mid);
build(rs, mid + 1, r);
pushup(rt);
}
void upd(int rt, int l, int r, int L, int R, int x) {
if (L <= l && r <= R) {
mx[rt] += x;
tag[rt] += x;
return;
}
pushdown(rt);
if (L <= mid) upd(ls, l, mid, L, R, x);
if (R > mid) upd(rs, mid + 1, r, L, R, x);
pushup(rt);
}
pair<ll, int> maxpos(int rt, int l, int r, int L, int R) {
if (L <= l && r <= R) return make_pair(mx[rt], mxpos[rt]);
pushdown(rt);
pair<ll, int> ret = {-1e18, 0};
if (L <= mid) ret = max(ret, maxpos(ls, l, mid, L, R));
if (R > mid) ret = max(ret, maxpos(rs, mid + 1, r, L, R));
return ret;
}
} seg2;
int main() {
freopen("peak.in", "r", stdin);
freopen("peak.out", "w", stdout);
cin.tie(0);
ios::sync_with_stdio(false);
int n; cin >> n;
rep(i, 1, n) cin >> a[i];
rep(i, 2, n) b[i] = a[i] - a[i - 1];
seg1.build(1, 2, n);
seg2.build(1, 1, n);
int q; cin >> q;
rep(i, 1, q) {
int op, l, r;
cin >> op >> l >> r;
if (op == 1) {
int x; cin >> x;
b[l] += x;
b[r + 1] -= x;
seg1.upd(1, 2, n, l);
seg2.upd(1, 1, n, l, r, x);
if (r + 1 <= n) seg1.upd(1, 2, n, r + 1);
} else if (op <= 4) {
if (l == r) cout << 1 << endl;
else cout << seg1.query(1, 2, n, l + 1, r, op - 2) << endl;
} else {
int pos = seg2.maxpos(1, 1, n, l, r).second;
if (pos == l || pos == r) {cout << 0 << endl; continue;}
bool resl = seg1.query(1, 2, n, l + 1, pos, 1);
bool resr = seg1.query(1, 2, n, pos + 1, r, 2);
cout << (resl && resr) << endl;
}
}
return 0;
}
#include<bits/stdc++.h>
#define LL long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
inline int read() {
char c=getchar();int x=0;while(c<'0'||c>'9')c=getchar();
while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-48,c=getchar();return x;
}
const int mod=998244353,maxn=100005;
struct sode{int l,r,v;}st[maxn],bl[maxn];
struct node{int l,r,x,v;}A[maxn*30],B[maxn*30];
struct Seg{int l,r,v;}seg[2][maxn];
int gcd(int a,int b) {return !b?a:gcd(b,a%b);}
inline int dqm(int x) {return x<0?x+mod:x;}
inline int qm(int x) {return x>=mod?x-mod:x;}
inline int cmp(const node &A,const node &B){
return A.v==B.v?A.x<B.x:A.v<B.v;
}
inline int ctp(const node &A,const node &B) {
return A.v==B.v?A.x>B.x:A.v<B.v;
}
int n,a[maxn],top,sa,sb,lp,sz[2],ans,pre[maxn];
int l[maxn*3],r[maxn*3],tag[maxn*3],d[maxn*3];
inline void pushup(int i) {d[i]=qm(d[i<<1]+d[i<<1|1]);}
inline void pushr(int i,int v) {
tag[i]=v;d[i]=1ll*(r[i]-l[i]+1)*v%mod;
}
inline void pushdown(int i) {
if(tag[i]==-1) return;pushr(i<<1,tag[i]);
pushr(i<<1|1,tag[i]);tag[i]=-1;
}
void bud(int x,int y,int i) {
l[i]=x,r[i]=y,tag[i]=-1;if(x==y) return;
int mid=x+y>>1;bud(x,mid,i<<1),bud(mid+1,y,i<<1|1);
}
void chg(int x,int y,int v,int i) {
if(x<=l[i]&&y>=r[i]) {pushr(i,v);return;}
int mid=l[i]+r[i]>>1;pushdown(i);
if(x<=mid) chg(x,y,v,i<<1);
if(y>mid) chg(x,y,v,i<<1|1);pushup(i);
}
int qry(int x,int y,int i) {
if(x<=l[i]&&y>=r[i]) return d[i];
int mid=l[i]+r[i]>>1;pushdown(i);
return qm((x<=mid?qry(x,y,i<<1):0)+(y>mid?qry(x,y,i<<1|1):0));
}
inline void ins(int l,int r,int v,int o) {
if(r>n)r=n;if(l<1)l=1;if(l>r) return;
seg[o][++sz[o]]=(Seg){l,r,v};
}
inline void calc(int l,int r,int v) {
pre[l]=qm(pre[l]+v),pre[r+1]=dqm(pre[r+1]-v);
}
inline void solve(int L,int R) {
int lst=0,v=0;sz[0]=sz[1]=0;
for(int i=L;i<=R;++i) {
chg(lst,A[i].x-1,v,1);
ins(lst+1,A[i].x,qm(v+1),0);
lst=A[i].x;
v=qm(v+qry(A[i].l-1,A[i].r-1,1));
v=qm(v+A[i].r-A[i].l+1);
}
chg(lst,n,v,1);
ins(lst+1,n+1,qm(v+1),0);
lst=n+1,v=0;int rp=lp;
while(lp<=sb&&B[lp].v==A[L].v) ++lp;
for(int i=rp;i<lp;++i) {
chg(B[i].x+1,lst,v,1);
ins(B[i].x,lst-1,qm(v+1),1);
lst=B[i].x;
v=qm(v+qry(B[i].l+1,B[i].r+1,1));
v=qm(v+B[i].r-B[i].l+1);
}
chg(1,lst,v,1);ans=qm(ans+v);
ins(0,lst-1,qm(v+1),1);
std::reverse(seg[1],seg[1]+sz[1]+1);
int x,y;x=0,y=0;
while(x<=sz[0]&&y<=sz[1]) {
calc(max(seg[0][x].l,seg[1][y].l),min(seg[0][x].r,seg[1][y].r),dqm(1ll*seg[0][x].v*seg[1][y].v%mod-1));
if(seg[0][x].r<seg[1][y].r) ++x;
else if(seg[0][x].r>seg[1][y].r) ++y;
else if(seg[0][x].r==seg[1][y].r) ++y,++x;
}
}
int main() {
freopen("selection.in", "r", stdin);
freopen("selection.out", "w", stdout);
n=read();
for(int i=1;i<=n;i++) a[i]=read();
for(int i=1;i<=n;i++) {
for(int j=1;j<=top;++j)
st[j].v=gcd(st[j].v,a[i]);
st[++top]=(sode){i,i,a[i]};
int tot=0,x=i,y=i;
for(int j=top-1;j>=0;--j) {
if(st[j].v!=st[j+1].v) {
bl[++tot].l=x,bl[tot].r=y;
bl[tot].v=st[j+1].v;
x=st[j].l,y=st[j].r;
}else x=st[j].l;
}
top=0;
while(tot) st[++top]=bl[tot--];
for(int j=1;j<=top;++j)
A[++sa]=(node){st[j].l,st[j].r,i,st[j].v};
}
top=0;
for(int i=n;i;i--) {
for(int j=1;j<=top;++j)
st[j].v=gcd(st[j].v,a[i]);
st[++top]=(sode){i,i,a[i]};
int tot=0,x=i,y=i;
for(int j=top-1;j>=0;--j)
if(st[j].v!=st[j+1].v) {
bl[++tot].l=x,bl[tot].r=y;
bl[tot].v=st[j+1].v;
x=st[j].l,y=st[j].r;
} else y=st[j].r;
top=0;
while(tot) st[++top]=bl[tot--];
for(int j=1;j<=top;++j)
B[++sb]=(node){st[j].l,st[j].r,i,st[j].v};
}
std::sort(A+1,A+sa+1,cmp);std::sort(B+1,B+sb+1,ctp);
int L=1;lp=1;
bud(0,n+1,1);
for(int i=2;i<=sa+1;++i)
if(A[i].v!=A[i-1].v)
solve(L,i-1),L=i;
for(int i=1;i<=n;i++)pre[i]=qm(pre[i-1]+pre[i]);
for(int i=1;i<=n;i++)printf("%d ",dqm(ans-pre[i]));
return 0;
}
kcs007