#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define pii pair<int,int>
#define vi vector<int>
#define fi first
#define se second
#define pb push_back
#define ALL(x) x.begin(),x.end()
#define sz(x) int(x.size())
#define ll long long
using namespace std;
const int N = 3e5 + 5,M = 1e6 + 50;
struct DSU{
vector <int> p,sz;
void init(int n){
p.resize(n);sz.assign(n,1);
iota(p.begin(),p.end(),0);
}
int find(int x){return p[x] == x ? x : p[x] = find(p[x]);}
void merge(int u,int v){
u = find(u),v = find(v);
if(u == v)return;
if(sz[u] > sz[v])swap(u,v);
p[u] = v,sz[v] += sz[u],sz[u] = 0;
}
}d;
int n;
int main(){
cin.tie(0)->sync_with_stdio(0);
cin >> n;
vi a(n);for(auto &x : a)cin >> x;
vector <vi> vec(M);
rep(i,0,n-1)vec[a[i]].pb(i);
vector <ll> cnt(M);
vi R(n,-1),L(n+1,-1);
auto getR = [&](int x){
if(x == n)return n;
return R[d.find(x)];
};
set <int> alive;
ll ans = 0,now = 0;//the amount of values <= i
d.init(n);
rep(i,1,M-1){
vector <int> dead,remove;
for(int x : alive){
int r = getR(x);
int nxtR = max(r,r == n ? -1 : getR(r));
if(nxtR == r)dead.pb(x);
else{
if(L[nxtR] != -1)dead.pb(x);
else{
L[nxtR] = x;
remove.pb(nxtR);
}
now += 1ll * (nxtR - r) * d.sz[d.find(x)];
R[d.find(x)] = nxtR;
}
}
for(int x : dead){
alive.erase(x);
if(L[getR(x)] == -1)L[getR(x)] = x;
else d.merge(L[getR(x)],x);
}
for(int x : remove)L[x] = -1;
for(int x : vec[i]){
++now;
R[x] = x + 1;
alive.insert(x);
if(L[x] != -1)alive.insert(L[x]);
L[x] = -1;
}
cnt[i] = now;
}
per(i,M-1,0)cnt[i] -= cnt[i-1];
rep(i,1,M-1)ans += cnt[i] * i;
cout << ans << 'n';
return 0;
}
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define pii pair<int,int>
#define vi vector<int>
#define fi first
#define se second
#define pb push_back
#define ALL(x) x.begin(),x.end()
#define sz(x) int(x.size())
#define ll long long
using namespace std;
const int N = 1e5 + 5;
int n,m,q,fa[N],out[N];
int find(int x){return fa[x] == x ? x : fa[x] = find(fa[x]);}
set <int> G[N],R[N];
bool chk(int x,int y){
x = find(x),y = find(y);
if(!fa[x] || !fa[y])return 1;//dead end
if(x == y)return 1;
return 0;
}
int main(){
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
int u,v;
rep(i,1,m){
cin >> u >> v;
out[u]++;
R[v].insert(u);//reverse graph
G[u].insert(v);
}
queue <int> Q;
rep(i,1,n){
fa[i] = i;
if(sz(G[i]) <= 1)Q.push(i);
}
while(!Q.empty()){//topo
int u = Q.front();
Q.pop();
int v = 0;
for(int x : G[u])if(find(x) != 0){
v = find(x);
break;
}
if(v == 0){//dead end
fa[u] = 0;
for(int x : R[u]){
--out[x];
if(out[x] == 1)Q.push(x);
}
}else{
//merge points of outdeg = 1
if(u == v)continue;
R[v].erase(u);
if(sz(R[u]) > sz(R[v]))swap(R[u],R[v]);
fa[u] = v;
for(int x : R[u]){
if(R[v].find(x) != R[v].end()){
--out[x];
if(out[x] == 1)Q.push(x);
}else R[v].insert(x);
}
}
R[u].clear();
}
cin >> q;
while(q--){
cin >> u >> v;
if(chk(u,v))putchar('B');
else putchar('H');
}
return 0;
}
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define pii pair<int,int>
#define vi vector<int>
#define fi first
#define se second
#define pb push_back
#define ll long long
using namespace std;
const int N = 3e5 + 5;
#define mid ((L + R) >> 1)
#define ls (p << 1)
#define rs (ls | 1)
struct SegTree{
int mx[N << 2];
void pushup(int p){mx[p] = max(mx[ls],mx[rs]);}
void modify(int p,int L,int R,int x,int v){
if(L == R){
mx[p] = max(mx[p],v);
return;
}
x <= mid ? modify(ls,L,mid,x,v) : modify(rs,mid + 1,R,x,v);
pushup(p);
}
int Q(int p,int L,int R,int l,int r){
if(r < L || R < l)return 0;
if(l <= L && R <= r)return mx[p];
return max(Q(ls,L,mid,l,r),Q(rs,mid + 1,R,l,r));
}
}f,g;
int n,a[N];
string s;
int main(){
cin.tie(0)->sync_with_stdio(0);
cin >> n;
rep(i,1,n)cin >> a[i];
cin >> s;
rep(i,1,n){
int U = f.Q(1,1,n,1,a[i]),D = g.Q(1,1,n,a[i],n);
U++,D++;
if(s[U - 1] == 'U')f.modify(1,1,n,a[i],U);
else g.modify(1,1,n,a[i],U);
if(s[D - 1] == 'U')f.modify(1,1,n,a[i],D);
else g.modify(1,1,n,a[i],D);
}
int ans = max(f.Q(1,1,n,1,n),g.Q(1,1,n,1,n));
cout << ans - 1 << 'n';
return 0;
}
【競賽報名/項目谘詢+微信：mollywei007】
評論已經被關(guan) 閉。