結果
| 問題 |
No.1788 Same Set
|
| コンテスト | |
| ユーザー |
 chocorusk
|
| 提出日時 | 2021-12-17 23:43:59 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,241 ms / 4,000 ms |
| コード長 | 5,658 bytes |
| コンパイル時間 | 4,069 ms |
| コンパイル使用メモリ | 195,984 KB |
| 最終ジャッジ日時 | 2025-01-27 02:43:39 |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 36 |
ソースコード
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#include <utility>
#include <functional>
#include <time.h>
#include <stack>
#include <array>
#include <list>
#include <atcoder/all>
#define popcount __builtin_popcount
using namespace std;
using namespace atcoder;
typedef long long ll;
typedef pair<int, int> P;
using mint=modint1000000007;
using ull=unsigned long long;
template<typename Monoid, typename OperatorMonoid=Monoid>
struct LazySegmentTree{
using F=function<Monoid(Monoid, Monoid)>;
using G=function<Monoid(Monoid, OperatorMonoid, int)>;
using H=function<OperatorMonoid(OperatorMonoid, OperatorMonoid)>;
int sz;
vector<Monoid> data;
vector<OperatorMonoid> lazy;
const F f;
const G g;
const H h;
const Monoid e1;
const OperatorMonoid e0;
LazySegmentTree(int n, const F f, const G g, const H h, const Monoid &e1, const OperatorMonoid &e0): f(f), g(g), h(h), e1(e1), e0(e0){
sz=1;
while(sz<n) sz<<=1;
data.resize(2*sz-1, e1);
lazy.resize(2*sz-1, e0);
}
void build(vector<Monoid> v){
for(int i=0; i<v.size(); i++) data[i+sz-1]=v[i];
for(int i=sz-2; i>=0; i--) data[i]=f(data[2*i+1], data[2*i+2]);
}
void eval(int k, int l, int r){
if(lazy[k]!=e0){
data[k]=g(data[k], lazy[k], r-l);
if(k<sz-1){
lazy[2*k+1]=h(lazy[2*k+1], lazy[k]);
lazy[2*k+2]=h(lazy[2*k+2], lazy[k]);
}
}
lazy[k]=e0;
}
void update(int a, int b, const OperatorMonoid &x, int k, int l, int r){
eval(k, l, r);
if(r<=a || b<=l) return;
if(a<=l && r<=b){
lazy[k]=h(lazy[k], x);
eval(k, l, r);
}else{
update(a, b, x, 2*k+1, l, (l+r)/2);
update(a, b, x, 2*k+2, (l+r)/2, r);
data[k]=f(data[2*k+1], data[2*k+2]);
}
}
void update(int a, int b, const OperatorMonoid &x){
return update(a, b, x, 0, 0, sz);
}
Monoid find(int a, int b, int k, int l, int r){
eval(k, l, r);
if(b<=l || r<=a) return e1;
if(a<=l && r<=b) return data[k];
else return f(find(a, b, 2*k+1, l, (l+r)/2), find(a, b, 2*k+2, (l+r)/2, r));
}
Monoid find(int a, int b){
return find(a, b, 0, 0, sz);
}
Monoid operator[](const int &k){
return find(k, k+1);
}
};
int n;
int a[400040], b[400040];
int pra[400040], prb[400040];
int v[400040];
const int sq=300;
int s[400040];
vector<int> vs[400040];
bool sorted[400040];
int main()
{
cin>>n;
for(int i=0; i<n; i++){
//a[i]=i%(n/2)+1;
cin>>a[i];
}
for(int i=0; i<n; i++){
//b[i]=i%(n/2)+1;
cin>>b[i];
}
fill(pra, pra+400040, -1);
fill(prb, prb+400040, -1);
ll ans=0;
// for(int i=0; i<n; i++){
// vs[i/sq].push_back(0);
// sorted[i/sq]=1;
// }
// auto add=[&](int l, int r, int x){//[l,r]
// int l1=l/sq, r1=r/sq;
// if(l1==r1){
// for(int i=l1*sq; i<(l1+1)*sq && i<n; i++){
// v[i]+=s[l1];
// if(l<=i && i<=r) v[i]+=x;
// vs[l1][i-l1*sq]=v[i];
// }
// s[l1]=0;
// sorted[l1]=0;
// return;
// }
// for(int i=l1*sq; i<(l1+1)*sq && i<n; i++){
// v[i]+=s[l1];
// if(l<=i) v[i]+=x;
// vs[l1][i-l1*sq]=v[i];
// }
// s[l1]=0;
// sorted[l1]=0;
// //sort(vs[l1].begin(), vs[l1].end());
// for(int i=r1*sq; i<(r1+1)*sq && i<n; i++){
// v[i]+=s[i];
// if(i<=r) v[i]+=x;
// vs[r1][i-sq*r1]=v[i];
// }
// s[r1]=0;
// sorted[r1]=0;
// //sort(vs[r1].begin(), vs[r1].end());
// for(int i=l1+1; i<r1; i++) s[i]+=x;
// };
// auto count=[&](int l, int r){
// int l1=l/sq, r1=r/sq;
// int res=0;
// if(l1==r1){
// for(int i=l; i<=r; i++){
// if(v[i]==-s[i]) res++;
// }
// return res;
// }
// for(int i=r1*sq; i<=r; i++){
// if(v[i]==-s[i]) res++;
// }
// for(int i=l1; i<r1; i++){
// if(s[i]) continue;
// if(!sorted[i]){
// sorted[i]=1;
// sort(vs[i].begin(), vs[i].end());
// }
// res+=upper_bound(vs[i].begin(), vs[i].end(), -s[i])-vs[i].begin();
// }
// return res;
// };
auto f=[&](P p1, P p2){
if(p1.first!=p2.first) return min(p1, p2);
else return P(p1.first, p1.second+p2.second);
};
auto g=[&](P p, int x, int len){
return P(p.first+x, p.second);
};
auto h=[&](int x, int y){
return x+y;
};
LazySegmentTree<P, int> seg(n, f, g, h, P(0, 0), 0);
vector<P> v0(n, P(0, 1));
seg.build(v0);
int l1, r1;
for(int i=0; i<n; i++){
l1=min(pra[a[i]], prb[a[i]])+1, r1=max(pra[a[i]], prb[a[i]])+1;
if(l1<=r1) seg.update(l1, r1, -1);
if(a[i]!=b[i]){
l1=min(pra[b[i]], prb[b[i]])+1, r1=max(pra[b[i]], prb[b[i]])+1;
if(l1<=r1) seg.update(l1, r1, -1);
}
pra[a[i]]=i, prb[b[i]]=i;
l1=min(pra[a[i]], prb[a[i]])+1, r1=max(pra[a[i]], prb[a[i]])+1;
if(l1<=r1) seg.update(l1, r1, 1);
if(a[i]!=b[i]){
l1=min(pra[b[i]], prb[b[i]])+1, r1=max(pra[b[i]], prb[b[i]])+1;
if(l1<=r1) seg.update(l1, r1, 1);
}
auto p=seg.find(0, i+1);
if(p.first==0) ans+=p.second;
}
cout<<ans<<endl;
return 0;
}