結果
問題 | No.1788 Same Set |
ユーザー |
![]() |
提出日時 | 2022-01-11 16:58:44 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 503 ms / 4,000 ms |
コード長 | 7,614 bytes |
コンパイル時間 | 1,358 ms |
コンパイル使用メモリ | 130,648 KB |
最終ジャッジ日時 | 2025-01-27 10:26:28 |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
#include<iostream>#include<array>#include<string>#include<cstdio>#include<vector>#include<cmath>#include<algorithm>#include<functional>#include<iomanip>#include<queue>#include<ciso646>#include<random>#include<map>#include<set>#include<complex>#include<bitset>#include<stack>#include<unordered_map>#include<utility>#include<tuple>#include<cassert>using namespace std;typedef long long ll;const ll mod = 1000000007;const ll INF = (ll)1000000007 * 1000000007;typedef pair<int, int> P;#define rep(i,n) for(int i=0;i<n;i++)#define per(i,n) for(int i=n-1;i>=0;i--)#define Rep(i,sta,n) for(int i=sta;i<n;i++)#define Per(i,sta,n) for(int i=n-1;i>=sta;i--)typedef long double ld;const ld eps = 1e-8;const ld pi = acos(-1.0);typedef pair<ll, ll> LP;int dx[4]={1,-1,0,0};int dy[4]={0,0,1,-1};template<class T>bool chmax(T &a, const T &b) {if(a<b){a=b;return 1;}return 0;}template<class T>bool chmin(T &a, const T &b) {if(b<a){a=b;return 1;}return 0;}template <class S,S (*op)(S, S),S (*e)(),class F,S (*mapping)(F, S),F (*composition)(F, F),F (*id)()>struct LazySegmentTree {// (*composition)は前が新たな作用素public:LazySegmentTree() : LazySegmentTree(0) {}LazySegmentTree(int n) : LazySegmentTree(std::vector<S>(n, e())) {}LazySegmentTree(const std::vector<S>& v) : _n(int(v.size())) {log = ceil_pow2(_n);size = 1 << log;d = std::vector<S>(2 * size, e());lz = std::vector<F>(size, id());for (int i = 0; i < _n; i++) d[size + i] = v[i];for (int i = size - 1; i >= 1; i--) {update_(i);}}void set(int p, S x) {assert(0 <= p && p < _n);p += size;for (int i = log; i >= 1; i--) push(p >> i);d[p] = x;for (int i = 1; i <= log; i++) update_(p >> i);}S get(int p) {assert(0 <= p && p < _n);p += size;for (int i = log; i >= 1; i--) push(p >> i);return d[p];}S query(int l, int r) {assert(0 <= l && l <= r && r <= _n);if (l == r) return e();l += size;r += size;for (int i = log; i >= 1; i--) {if (((l >> i) << i) != l) push(l >> i);if (((r >> i) << i) != r) push(r >> i);}S sml = e(), smr = e();while (l < r) {if (l & 1) sml = op(sml, d[l++]);if (r & 1) smr = op(d[--r], smr);l >>= 1;r >>= 1;}return op(sml, smr);}S all_query() { return d[1]; }void update(int p, F f) {assert(0 <= p && p < _n);p += size;for (int i = log; i >= 1; i--) push(p >> i);d[p] = mapping(f, d[p]);for (int i = 1; i <= log; i++) update_(p >> i);}void update(int l, int r, F f) {assert(0 <= l && l <= r && r <= _n);if (l == r) return;l += size;r += size;for (int i = log; i >= 1; i--) {if (((l >> i) << i) != l) push(l >> i);if (((r >> i) << i) != r) push((r - 1) >> i);}{int l2 = l, r2 = r;while (l < r) {if (l & 1) all_apply(l++, f);if (r & 1) all_apply(--r, f);l >>= 1;r >>= 1;}l = l2;r = r2;}for (int i = 1; i <= log; i++) {if (((l >> i) << i) != l) update_(l >> i);if (((r >> i) << i) != r) update_((r - 1) >> i);}}template <bool (*g)(S)> int max_right(int l) {return max_right(l, [](S x) { return g(x); });}template <class G> int max_right(int l, G g) {assert(0 <= l && l <= _n);assert(g(e()));if (l == _n) return _n;l += size;for (int i = log; i >= 1; i--) push(l >> i);S sm = e();do {while (l % 2 == 0) l >>= 1;if (!g(op(sm, d[l]))) {while (l < size) {push(l);l = (2 * l);if (g(op(sm, d[l]))) {sm = op(sm, d[l]);l++;}}return l - size;}sm = op(sm, d[l]);l++;} while ((l & -l) != l);return _n;}template <bool (*g)(S)> int min_left(int r) {return min_left(r, [](S x) { return g(x); });}template <class G> int min_left(int r, G g) {assert(0 <= r && r <= _n);assert(g(e()));if (r == 0) return 0;r += size;for (int i = log; i >= 1; i--) push((r - 1) >> i);S sm = e();do {r--;while (r > 1 && (r % 2)) r >>= 1;if (!g(op(d[r], sm))) {while (r < size) {push(r);r = (2 * r + 1);if (g(op(d[r], sm))) {sm = op(d[r], sm);r--;}}return r + 1 - size;}sm = op(d[r], sm);} while ((r & -r) != r);return 0;}private:int _n, size, log;std::vector<S> d;std::vector<F> lz;void update_(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }void all_apply(int k, F f) {d[k] = mapping(f, d[k]);if (k < size) lz[k] = composition(f, lz[k]);}void push(int k) {all_apply(2 * k, lz[k]);all_apply(2 * k + 1, lz[k]);lz[k] = id();}int ceil_pow2(int n) {int x = 0;while ((1U << x) < (unsigned int)(n)) x++;return x;}};P f(P a,P b){if(a.first==b.first){return P(a.first,a.second+b.second);}if(a.first>b.first){return b;}return a;}P e(){return P(mod,0);}P g(int a,P b){return P(a+b.first,b.second);}int h(int a,int b){return a+b;}int id(){return 0;}int n,m=400005;int a[200010],b[200010];int p[400010],q[400010];void solve(){cin >> n;rep(i,n) {cin >> a[i];a[i]--;}rep(i,n) {cin >> b[i];b[i]--;}rep(i,m){p[i]=-1;q[i]=-1;}ll A=0;LazySegmentTree<P,f,e,int,g,h,id> seg(vector<P>(n,P(0,1)));rep(r,n){//cout << r << endl;int mi=min(p[a[r]],q[a[r]]),ma=max(p[a[r]],q[a[r]]);//cout << "pre:" << mi << " " << ma << endl;if(mi+1<=ma){seg.update(mi+1,ma+1,-1);}if(a[r]!=b[r]){mi=min(p[b[r]],q[b[r]]),ma=max(p[b[r]],q[b[r]]);//cout << "pre:" << mi << " " << ma << endl;if(mi+1<=ma){seg.update(mi+1,ma+1,-1);}}p[a[r]]=r;q[b[r]]=r;mi=min(p[a[r]],q[a[r]]),ma=max(p[a[r]],q[a[r]]);if(mi+1<=ma){//cout << "new:" << mi << " " << ma << endl;seg.update(mi+1,ma+1,1);}if(a[r]!=b[r]){mi=min(p[b[r]],q[b[r]]),ma=max(p[b[r]],q[b[r]]);//cout << "new:" << mi << " " << ma << endl;if(mi+1<=ma){seg.update(mi+1,ma+1,1);}}P ans=seg.query(0,r+1);//cout << ans.first << " " << ans.second << endl;if(ans.first==0) A+=ans.second;}cout << A << endl;}int main(){ios::sync_with_stdio(false);cin.tie(0);cout << fixed << setprecision(50);solve();}