2018-team2

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

[[PageOutline]]

[[Image(恋恋.jpg,800px)]] [[br]]
[[Image(wiki:2018-team2:ChiJiang.jpg,500px)]]

== 队伍信息 ==

 * 队名：'''EuropeSun'''
 * 成员：
   * 欧阳逸飞 (lqybzx)
   * 王宇晗 (Johann)
   * 张鑫 (zx2018)

== 训练账号 ==

 * ACM/ICPC Live Archive: ???
 * Codeforces: 
 * Virtual Judge: 

== 定个小目标 ==
 * 先学会后缀数组后缀自动机相关？
 * 让zx转变成ACM选手
 * 多训练多写题多练习
 * ~~让约翰有lyk一半聪明~~

trojan://AP8VUpNarCJnyYzEPt@fm1-2.sstr-api.xyz:443
https://github.com/marlam/camsim-mirror

#include<bits/stdc++.h>
using namespace std;

int n,tl,tr,a[200000],b[200000],tt,f[200000],c[300000],c1[300000],c2[300000],t,d[200000],pt,d1[200000],d2[200000],e1[200000],e2[200000];

void find(int x){
    for (;tt<=n&&a[tt]!=x;tt++);
    if (tt>n) {
        cout << -1 << endl;
        exit(0);
    }
    d[++pt]=tt;
    d1[pt]=tl;
    d2[pt]=tr;
}

void solve(int i,int tl,int tr){
    int tt=d[i];
    int x=a[tt];
    int l=tt,r=tt;

    //cout << tl << " " << tr << endl;
    while (l>tl||r<tr){
        //cout << l << " " << r << endl;
        if (l>tl){
        if (a[l-1]<x){
            while (l>tl&&a[l-1]<x) {l--;if (f[l]) l=tl;}
            while (r<tr&&a[r+1]<x) {r++;if (f[r]) r=tr;}
            f[l]=f[r]=1;
            a[l]=a[r]=x;
            c[++t]=1,c1[t]=l,c2[t]=r;
        }else{
            while (l>tl&&a[l-1]>x) {l--;if (f[l]) l=tl;}
            while (r<tr&&a[r+1]>x) {r++;if (f[r]) r=tr;}
            f[l]=f[r]=1;
            a[l]=a[r]=x;
            c[++t]=0,c1[t]=l,c2[t]=r;
        }
        }
        //cout << l << " " << r << endl;
        if (r<tr){
        if (a[r+1]<x){
            while (l>tl&&a[l-1]<x) {l--;if (f[l]) l=tl;}
            while (r<tr&&a[r+1]<x) {r++;if (f[r]) r=tr;}
            f[l]=f[r]=1;
            a[l]=a[r]=x;
            c[++t]=1,c1[t]=l,c2[t]=r;
        }else{
            while (l>tl&&a[l-1]>x) {l--;if (f[l]) l=tl;}
            while (r<tr&&a[r+1]>x) {r++;if (f[r]) r=tr;}
            f[l]=f[r]=1;
            a[l]=a[r]=x;
            c[++t]=0,c1[t]=l,c2[t]=r;
        }
        }
        //cout << l << " " << r << endl;
    }
    e1[i]=l;
    e2[i]=r;
}

void solve1(int tt,int tl,int tr,int l,int r){
    int x=a[tt];
    //cout << x << " " << tl << " " << tr << " " << l << " " << r << endl;
    //cout << tl << " " << tr << endl;
    while (l>tl||r<tr){
        //cout << l << " " << r << endl;
        if (l>tl){
        if (a[l-1]<x){
            while (l>tl&&a[l-1]<x) {l--;if (f[l]) l=tl;}
            while (r<tr&&a[r+1]<x) {r++;if (f[r]) r=tr;}
            f[l]=f[r]=1;
            a[l]=a[r]=x;
            c[++t]=1,c1[t]=l,c2[t]=r;
        }else{
            while (l>tl&&a[l-1]>x) {l--;if (f[l]) l=tl;}
            while (r<tr&&a[r+1]>x) {r++;if (f[r]) r=tr;}
            f[l]=f[r]=1;
            a[l]=a[r]=x;
            c[++t]=0,c1[t]=l,c2[t]=r;
        }
        }
        //cout << l << " " << r << endl;
        if (r<tr){
        if (a[r+1]<x){
            while (l>tl&&a[l-1]<x) {l--;if (f[l]) l=tl;}
            while (r<tr&&a[r+1]<x) {r++;if (f[r]) r=tr;}
            f[l]=f[r]=1;
            a[l]=a[r]=x;
            c[++t]=1,c1[t]=l,c2[t]=r;
        }else{
            while (l>tl&&a[l-1]>x) {l--;if (f[l]) l=tl;}
            while (r<tr&&a[r+1]>x) {r++;if (f[r]) r=tr;}
            f[l]=f[r]=1;
            a[l]=a[r]=x;
            c[++t]=0,c1[t]=l,c2[t]=r;
        }
        }
        //cout << l << " " << r << endl;
    }
}

void dfs(int x){
    if (x>pt) return;
    //cout << x << endl;
    if (x<=pt&&d2[x]>=d[x+1]-1) {dfs(x+1);solve1(d[x],d1[x],d2[x],e1[x],e2[x]);}
    else {solve1(d[x],d1[x],d2[x],e1[x],e2[x]);dfs(x+1);}

}

int main(){
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];
    for (int i = 1; i <= n; i++){
        if (b[i]!=b[i-1]){
            if (i>1) find(b[i-1]);
            tl=tr=i;
        } else tr++;
    }
    find(b[n]);
    d[pt+1]=n+1;
    for (int i = 1; i <= pt; i++) if (i==1) solve(i,1,d[i+1]-1); else solve(i,d[i],d[i+1]-1);
    d[1]=1;
    //cout << pt << endl;
    dfs(1);
    cout << t << endl;
    for (int i = 1; i <= t; i++){
        if (c[i]) cout << "M " << c1[i] << " " << c2[i] << endl;
        else cout << "m " << c1[i] << " " << c2[i] << endl;
    }
    return 0;
}
/*
5
1 5 5 3 4
1 1 4 4 4

5
1 2 3 4 4
2 2 2 2 5

10
7 7 7 7 7 7 3 4 5 6
3 3 3 4 4 4 5 5 5 5

10
1 11 12 13 2 14 15 3 16 17
1 1 1 1 1 1 1 1 2 3
*/
== 杂事杂项 ==

避免sqrt
权值线段树下去才开，下去才开，传递L，R。

== 板子整理 ==

1. [http://rng-58.blogspot.com/2017/02/hashing-and-probability-of-collision.html rng_58 Hash]

'''曼哈顿距离最小生成树''' ☆

'''欧拉距离最小生成树''' ☆

'''k圆并''' ☆

'''k短路''' ☆

'''杜教筛'''

'''JAVA与高精度'''

'''主席树带修改''' ☆

'''hash板子 9.14-I暴力''' ☆

'''log 质因数分解'''☆

'''线性求逆'''

'''linux对拍'''☆

'''LCT区间加乘 LCT维护子树 LCT维护边权'''☆

'''魔法森林''' ☆

'''exlucas+中国剩余定理'''

'''SAM'''

== 个人训练 ==


== 团队训练 ==
 1. [http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=006517 2018-03-03] [wiki:2018-sp01-team3 Summary] 2015 - ICPC - NEERC - Central Subregional
 2. [http://codeforces.com/gym/101615 2018-03-04] [wiki:2018-sp02-team3 Summary] 2017 - ACM-ICPC Pacific Northwest Regional Contest (Div. 1)
 3. [http://opentrains.snarknews.info/~ejudge/team.cgi?SID=5309a9b1dc6d5381&action=2&lt=1 2018-03-09] [wiki:2018-sp03-team3 Summary] 2017 - ICPC - Asia - Tsukuba
 4. [https://vjudge.net/contest/216811#overview 2018-03-16] [wiki:2018-sp04-team3 Summary] Rocky Mountains 2016
 5. [https://vjudge.net/contest/216426#overview 2018-03-17] [wiki:2018-sp05-team3 Summary] 2018 Zhejiang U Summer Training Camp, Legilimens Contest 1
 6. [http://opentrains.snarknews.info/~ejudge/team.cgi?SID=d31b0dc0a6396027&action=2&lt=1 2018-03-30] [wiki:2018-sp06-team3 Summary] Petrozavodsk Winter-2016. JAG Contest
 7. [http://opentrains.snarknews.info/~ejudge/team.cgi?SID=9d1db4ab7986edb3&action=2 2018-04-05] [wiki:2018-sp07-team3 Summary] XVI Open Cup - Grand Prix of Spb
 8. [http://opentrains.snarknews.info/~ejudge/team.cgi?SID=aae92186fc98a1d1&action=2&lt=1 2018-04-13] [wiki:2018-sp08-team3 Summary] Petrozavodsk Summer-2017. Warsaw U Contest, XVII OpenCup Onsite
 9. [http://opentrains.snarknews.info/~ejudge/team.cgi?SID=e19896dc91b1b0f8&action=2&lt=1 2018-04-20] [wiki:2018-sp09-team3 Summary] Makoto Soejima Contest 3 (MIPT Workshop Open 2)
 10. [http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=006259 2018-04-22] [wiki:2018-sp10-team3 Summary] 2014 - ICPC - Asia - Tokyo
 11. [http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=001519 2018-04-27] [wiki:2018-sp11-team3 Summary] Petrozavodsk Winter-2018. Carnegie Mellon U Contest
 12. [http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=006571 2018-05-11] [wiki:2018-sp12-team3 Summary] Moscow Subregional 2014
 13. [http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=010353 2018-05-13] [wiki:2018-sp13-team3 Summary] XVII Open Cup named after E.V. Pankratiev. Grand Prix of SPb.
 14. [http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=010312 2018-05-20] [wiki:2018-sp14-team3 Summary] 2015 - XVI Open Cup named after E.V. Pankratiev. GP of Japan.
 15. [http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=010317 2018-06-01] [wiki:2018-Sp15-team3 Summary] 2015 - XVI Open Cup - Grand Prix of Europe (CEPC-2015)
 16. [http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=010311 2018-06-08] [wiki:2018-Sp16-team3 Summary] 2015 - XVI Open Cup named after E.V. Pankratiev. GP of Ukraine
 17. [http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=010313 2018-06-10] [wiki:2018-Sp17-team3 Summary] 2015 - XVI Open Cup named after E.V. Pankratiev. GP of Eurasia
 18. [http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=010316 2018-06-15] [wiki:2018-Sp18-team3 Summary] 2015 - XVI Open Cup named after E.V. Pankratiev. GP of Siberia
 19. [http://codeforces.com/group/J1GbXiu37w/contest/226796 2018-08-09] [wiki:2018-Sp19-team3 Summary] 2017 - ICPC - Europe - SWERC
 20. [http://10.71.10.90/pia/trac/wiki/2018-C02 2018-08-10] [wiki:2018-Sp20-team3 Summary] 2010 - German Collegiate Programming Contest
 21. [http://10.71.10.90/pia/trac/wiki/2018-C03 2018-08-11] [wiki:2018-Sp21-team3 Summary] Petrozavodsk Winter-2013. Andrew Stankevich Contest 43
 22. [http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=001413 2018-08-12] [wiki:2018-Sp22-team3 Summary] Petrozavodsk Winter-2013. Andrew Stankevich Contest 43
 23. [http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=001413 2018-08-14] [wiki:2018-Sp23-team3 Summary] 2018 - Multi-University Training - Contest 7 by UESTC
 24. [http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=001413 2018-08-15] [wiki:2018-Sp24-team3 Summary] 2017 - ICPC - Europe - NEERC - Northern Subregional
 25. [http://10.71.10.90/pia/trac/wiki/2018-C07 2018-08-16] [wiki:2018-Sp25-team3 Summary] 2017 - ICPC - Europe - CERC
 26. [http://10.71.10.90/pia/trac/wiki/2018-C08 2018-08-17] [wiki:2018-Sp26-team3 Summary] 2014 - Moscow IPT Training Camp - JAG Autumn Contest
 27. [http://10.71.10.90/pia/trac/wiki/2018-C09 2018-08-18] [wiki:2018-Sp27-team3 Summary] 2014 - ICPC - Europe - NEERC
 28. [http://10.71.10.90/pia/trac/wiki/2018-C10 2018-08-20] [wiki:2018-Sp28-team3 Summary] 2015 - Moscow International ACM ICPC Workshop - AMPPZ-2015
 29. [http://10.71.10.90/pia/trac/wiki/2018-C11 2018-08-21] [wiki:2018-Sp29-team3 Summary] 2017 - ICPC - Europe - NEERC
 30. [http://10.71.10.90/pia/trac/wiki/2018-C12 2018-08-22] [wiki:2018-Sp30-team3 Summary] 2018 - Multi-University Training - Contest 8 by NJU
 31. [http://10.71.10.90/pia/trac/wiki/2018-C13 2018-08-23] [wiki:2018-Sp31-team3 Summary] 2015 - Moscow International ACM ICPC Workshop - AIM Fund Contest
 32. [http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=001397 2018-08-28] [wiki:2018-Sp32-team3 Summary] 2012-Petrozavodsk Winter. Tokyo Kroliki Contest
 33. [http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=001424 2018-08-29] [wiki:2018-Sp33-team3 Summary] Petrozavodsk Summer-2013. Comenius U Selection by Michal Forisek.
 34. [wiki:2018-C14 2018-08-25] [wiki:2018-Sp34-team3 Summary] 2018 - CCPC - Online
 35. [https://www.jisuanke.com/contest/1556?view=challenges 2018-09-08] [wiki:2018-Sp35-team3 Summary]2018 - ICPC - Asia - Shenyang - Online
 36. [https://www.jisuanke.com/contest/1557 2018-09-09] [wiki:2018-Sp36-team3 Summary]2018 - ICPC - Asia - Xuzhou - Online
 37. [http://codeforces.com/gym/100402/attachments 2018-09-11] [wiki:2018-Sp37-team3 Summary]Andrew Stankevich Contest 32 Petrozavodsk Summer Training Camp
 38. [http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=010410 2018-09-12] [wiki:2018-Sp38-team3 Summary]2018 - XVIII Open Cup named after E.V. Pankratiev. Grand Prix of Korea
 39. [http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=001451 2018-09-13] [wiki:2018-Sp39-team3 Summary] Petrozavodsk Winter-2015. Xiaoxu Guo Contest 3.
 40. [https://www.jisuanke.com/contest/1558?view=challenges 2018-09-15] [wiki:2018-Sp40-team3 Summary] 2018 - ICPC - Asia - Jiaozuo - Online
 41. [http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=001451 2018-09-16] [wiki:2018-Sp41-team3 Summary] 2018 - ICPC - Asia - Qingdao - Online
 42. [http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=001489 2018-09-19] [wiki:2018-Sp42-team3 Summary] XVII Open Cup named after E.V. Pankratiev. Grand Prix of Japan.
 43. [http://acm.pku.edu.cn/icpc_pku2015/ 2018-09-22] [wiki:2018-Sp43-team3 Summary] - 2018 ICPC Asia Beijing Online
 44. [http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=010354 2018-09-24] [wiki:2018-Sp44-team3 Summary] XVII Open Cup named after E.V. Pankratiev. Eastern Grand Prix.
 45. [http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=001468 2018-09-26] [wiki:2018-Sp45-team3 Summary] Petrozavodsk Summer-2015. Warsaw U Tasks, XV Open Cup Onsite
 46. [https://vjudge.net/contest/257494 2018-09-28] [wiki:2018-Sp46-team3 Summary] 2015 - ICPC - Changchun
 47. [http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=006283 2018-09-30] [wiki:2018-Sp47-team3 Summary] Moscow Pre-Finals Workshop 2016. Kent Nikaido Contest 1
 48. [http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=001427 2018-10-01] [wiki:2018-Sp48-team3 Summary] Petrozavodsk Summer-2013. (ETH Zurich)+ Contest
 49. [http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=01374 2018-10-02] [wiki:2018-Sp49-team3 Summary] Petrozavodsk Winter-2011. Moscow IPT Contest.
 50. [http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=010229 2018-10-03] [wiki:2018-Sp50-team3 Summary] 2013 - 0x11 Ural Championship: Battle of Giants
 51. [https://vjudge.net/contest/261394 2018-10-12] [wiki:2018-Sp51-team3 Summary] 2015 ShenYang Onsite 
 52. [https://vjudge.net/contest/261634#overview 2018-10-13] [wiki:2018-Sp52-team3 Summary] 2016 ccpc hefei
 53. [http://codeforces.com/gym/100959#overview 2018-10-17] [wiki:2018-Sp53-team3 Summary] 2015-2016 Petrozavodsk Winter Training Camp, Makoto rng_58 Soejima Сontest 4
 54. [https://vjudge.net/contest/263732 2018-10-19] [wiki:2018-Sp54-team3 Summary] 2017 shenyang ICPC
 55.  [http://codeforces.com/group/J1GbXiu37w/contest/230452 2018-10-24] [wiki:2018-Sp55-team3 Summary] 2016-17 NTU WF Selecting Contest
 56.  [https://vjudge.net/contest/267726#overview 2018-11-03] [wiki:2018-Sp56-team3 Summary] 2015 - ICPC - EC FINAL  
 57.  [http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=010252 2018-11-09] [wiki:2018-Sp57-team3 Summary] XIV Open Cup named after E.V. Pankratiev. GP of America.
 58.  [http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=010315 2018-11-10] [wiki:2018-Sp58-team3 Summary] XVI Open Cup named after E.V. Pankratiev. GP of Ekaterinburg.
 58.  [http://codeforces.com/gym/101873 2018-11-13] [wiki:2018-Sp59-team3 Summary]2017-2018 ACM-ICPC German Collegiate Programming Contest (GCPC 2017)


= 比赛记录 ==
 1. [http://acm.zju.edu.cn/contest-materials/zju2018/board/ 2018-04-07] [wiki:2018-c01-team3 Summary] - 2018 ZJUPC
 2. [http://acm.zju.edu.cn/zjp2018/board/ 2018-04-29] [wiki:2018-c02-team3 Summary] - 2018 ZJPC
 3. [https://www.cc98.org/topic/4798791/ 2018-10-21] [wiki:2018-c03-team3 Summary] - 2018 ACM/ICPC ShenYang Onsite
 4. [https://www.cc98.org/topic/4798791/ 2018-10-21] [wiki:2018-c04-team3 Summary] - 2018 CCPC Guilin Onsite
== 补题 ==

|| Contest Name                           || A || B || C || D || E || F || G || H || I || J || K || L || M ||
|| 2015 - ICPC - NEERC - Central Subregional || O || O || Ø || O || # || . || Ø || O || O || O || O || X || X ||
|| 2017 - ACM-ICPC Pacific Northwest Regional Contest (Div. 1) || O || . || O || Ø || O || Ø || O || Ø || . || O || . || O || O ||
|| 2017 - ICPC - Asia - Tsukuba || O || O || O || . || Ø || O || . || Ø || O || Ø || Ø || X || X ||
|| Rocky Mountains 2016 || O || O || O || O || O || O || O || O || O || O || X || X || X ||
|| 2018 Zhejiang U Summer Training Camp, Legilimens Contest 1 || O || O || O || . || Ø || O || . || . || O || O || O || X || X ||
|| Petrozavodsk Winter-2016. JAG Contest || O || O || O || O || O || Ø || Ø || O || . || .. || Ø || X || X ||
|| XVI Open Cup - Grand Prix of Spb || O || . || . || O || O || . || . || O || O || O || . || . || X ||
|| 2018 ZJUPC || O || . || O || O || . || O || O || O || . || O || X || X || X ||
|| Petrozavodsk Summer-2017. Warsaw U Contest, XVII OpenCup Onsite || Ø || Ø || O || O || . || . || O || O || . || O || O || X || X ||
|| Makoto Soejima Contest 3 (MIPT Workshop Open 2) || Ø || O || Ø || Ø || Ø || . || O || O || . || . || . || X || X ||
|| 2014 - ICPC - Asia - Tokyo || O || O || O || O || O || O || O || . || Ø || . || . || X || X ||
|| Petrozavodsk Winter-2018. Carnegie Mellon U Contest || Ø || O || Ø || Ø || . || O || . || O || Ø || Ø || . || X || X ||
|| 2018 ZJPC || O || O || # || O || O || O || . || . || O || O || O || O || O ||
|| Moscow Subregional 2014 || O || Ø || O || O || O || O || O || Ø || Ø || . || . || . || X ||
|| XVII Open Cup named after E.V. Pankratiev. Grand Prix of SPb. || O || O || . || O || O || O || O || O || . || .. || O || X || X ||
|| 2015 - XVI Open Cup named after E.V. Pankratiev. GP of Japan. || O || O || . || O || . || O || O || Ø || Ø || Ø || X || X || X ||
|| 2015 - XVI Open Cup - Grand Prix of Europe (CEPC-2015) || O || O || . || O || Ø || Ø || . || O || Ø || Ø || O || . || X ||
|| 2015 - XVI Open Cup named after E.V. Pankratiev. GP of Ukraine || O || O || O || O || Ø || O || O || . || . || . || O || . || O ||
|| 2015 - XVI Open Cup named after E.V. Pankratiev. GP of Eurasia || O || O || O || O || O || O || . || O || O || . || O || Ø || X ||
|| 2015 - XVI Open Cup named after E.V. Pankratiev. GP of Siberia || O || O || O || O || O || . || Ø || O || . || O || O || . || X ||
|| 2017 - ICPC - Europe - SWERC || O || O || O || # || O || O || O || . || . || O || O || X || X ||
|| 2017 - ICPC - Europe - NEERC - Moscow Subregional  || O || . || O || O || . || O || O || O || . || . || . || X || X ||
|| Petrozavodsk Winter-2013. Andrew Stankevich Contest 43 || . || O || . || # || . || . || . || O || O || O || O || O || X ||
|| 2018 - Multi-University Training - Contest 7 by UESTC || Ø || . || . || . || O || Ø || . || Ø || O || O || O || X || X ||
|| 2017 - ICPC - Europe - NEERC - Northern Subregional || O || O || O || . || O || . || O || O || O || . || O || O || X ||
|| 2017 - ICPC - Europe - CERC || O || . || . || . || . || O || . || O || . || O || . || O || X ||
|| 2014 - Moscow IPT Training Camp - JAG Autumn Contest || O || O || . || O || . || Ø || O || . || . || O || O || X || X ||
|| 2014 - ICPC - Europe - NEERC || O || O || . || Ø || Ø || O || . || . || O || O || O || X || X ||
|| 2015 - Moscow International ACM ICPC Workshop - AMPPZ-2015 || Ø || # || . || O || . || O || . || Ø || O || . || . || Ø || X ||
|| 2017 - ICPC - Europe - NEERC || O || O || O || O || O || Ø || . || . || . || . || . || # || X ||
|| 2018 - Multi-University Training - Contest 8 by NJU || O || O || . || O || O || . || . || . || . || O || . || Ø || X ||
|| 2015 - Moscow International ACM ICPC Workshop - AIM Fund Contest || O || # || # || . || O || Ø || O || O || O || O || # || X || X ||
|| 2012 - Petrozavodsk Winter. Tokyo Kroliki Contest || . || # || O || O || . || . || O || O || . || O || .|| X || X ||
|| Petrozavodsk Summer-2013. Comenius U Selection by Michal Forisek. || O || O || # || . || O || O || O || . || X || X || X|| X || X ||
|| 2018 - CCPC - Online || O || . || O || O || O || . || O || . || O || O || X || X || X ||
|| 2018 - ICPC - Asia - Shenyang - Online || . || . || O || O || O || O || O || . || O || Ø || O || X || X ||
|| 2018 - ICPC - Asia - Xuzhou - Online || O || O || O || Ø || # || O || O || O || O || O || O || X || X ||
|| Andrew Stankevich Contest 32 Petrozavodsk Summer Training Camp || O || O || O || O || Ø || O || O || . || . || Ø || O || X || X ||
|| 2018 - XVIII Open Cup named after E.V. Pankratiev. Grand Prix of Korea || Ø || . || O || O || . || O || . || . || . || . || . || Ø || X ||
|| Petrozavodsk Winter-2015. Xiaoxu Guo Contest 3. || Ø || O || . || . || O || Ø || O || . || Ø || O || X || X || X ||
|| 2018 - ICPC - Asia - Jiaozuo - Online || O || O || . || Ø || O || O || O || O || O || O || O || X || X ||
|| 2018 - ICPC - Asia - Qingdao - Online || O || # || O || # || . || Ø || O || . || . || O || O || X || X ||
|| XVII Open Cup named after E.V. Pankratiev. Grand Prix of Japan. || . || . || . || O || . || . || . || O || . || . || X || X || X ||
|| 2018 ICPC Asia Beijing Online || O || O || O || O || . || . || . || O || . || . || X || X || X ||
|| XVII Open Cup named after E.V. Pankratiev. Eastern Grand Prix. || O || O || . || O || O || O || O || O || O || . || . || O || X ||
|| Petrozavodsk Summer-2015. Warsaw U Tasks, XV Open Cup Onsite || . || O || # || . || O || . || . || O || O || . || . || X || X ||
|| 2015 - ICPC - Changchun || Ø || O || . || . || O || O || O || O || . || O || . || O || X ||
|| Moscow Pre-Finals Workshop 2016. Kent Nikaido Contest 1 || O || . || . || O || . || . || . || O || . || O || O || X || X ||
|| Petrozavodsk Summer-2013. (ETH Zurich)+ Contest || O || O || O || . || . || O || . || O || O || O || . || O || X ||
|| 0x11 Ural Championship: Battle of Giants. || O || O || . || . || O || . || . || O || O || O || . || . || X ||
|| 2015 ShenYang Onsite || . || O || . || O || . || . || Ø || . || O || . || . || . || O ||
|| 2016 ccpc hefei || O || . || O || O || O || . || Ø || O || O || Ø || X || X || X ||
|| 2015-2016 Petrozavodsk Winter Training Camp, Makoto rng_58 Soejima Сontest4 || . || O || O || . || O || # || . || . || # || O || . || O || . ||
|| 2017 shenyang ICPC || . || . || O || . || . || O || . || . || O || . || O || O || O ||
|| 2018 ACM/ICPC ShenYang Onsite|| . || . || O || . || O || . || O || . || . || O || . || O || . ||
|| 2016-17 NTU WF Selecting Contest || O || Ø || O || . || . || . || O || . || Ø || O || . || . || . ||
|| 2018 CCPC Guilin Onsite || Ø || . || . || O || . || . || O || O || . || O || . || O || X ||
|| 2015 - ICPC - EC FINAL || O || O || . || O || . || O || . || . || . || O || . || O || O ||
|| XIV Open Cup named after E.V. Pankratiev. GP of America.|| O || . || O || O || . || . || O || O || O || O || X || X || X ||
|| XVI Open Cup named after E.V. Pankratiev. GP of Ekaterinburg. || . || O || O || O || O || O || O || . || . || O || . || X || X ||
|| 2017-2018 ACM-ICPC German Collegiate Programming Contest (GCPC 2017) || Ø || O || O || O || O || O || O || Ø || O || O || O || X || X ||

O:当场通过 .:尚未通过 Ø:赛后通过 #:口胡通过 X:不存在的 ..:想去补的没过题留个标记……

[[PageOutline]]

[[br]]

队伍信息

  • 队名：EuropeSun
  • 成员：
    • 欧阳逸飞 (lqybzx)
    • 王宇晗 (Johann)
    • 张鑫 (zx2018)

训练账号

  • ACM/ICPC Live Archive: ???
  • Codeforces:
  • Virtual Judge:

定个小目标

  • 先学会后缀数组后缀自动机相关？
  • 让zx转变成ACM选手
  • 多训练多写题多练习
  • 让约翰有lyk一半聪明

trojan://AP8VUpNarCJnyYzEPt@fm1-2.sstr-api.xyz:443

https://github.com/marlam/camsim-mirror

#include

using namespace std;

int n,tl,tr,a[200000],b[200000],tt,f[200000],c[300000],c1[300000],c2[300000],t,d[200000],pt,d1[200000],d2[200000],e1[200000],e2[200000];

void find(int x){

for (;tt<=n&&a[tt]!=x;tt++);

if (tt>n) {

cout << -1 << endl;

exit(0);

}

d[++pt]=tt;

d1[pt]=tl;

d2[pt]=tr;

}

void solve(int i,int tl,int tr){

int tt=d[i];

int x=a[tt];

int l=tt,r=tt;

//cout << tl << " " << tr << endl;

while (l>tl||r

//cout << l << " " << r << endl;

if (l>tl){

if (a[l-1]

while (l>tl&&a[l-1]

while (r

f[l]=f[r]=1;

a[l]=a[r]=x;

c[++t]=1,c1[t]=l,c2[t]=r;

}else{

while (l>tl&&a[l-1]>x) {l--;if (f[l]) l=tl;}

while (rx) {r++;if (f[r]) r=tr;}

f[l]=f[r]=1;

a[l]=a[r]=x;

c[++t]=0,c1[t]=l,c2[t]=r;

}

}

//cout << l << " " << r << endl;

if (r

if (a[r+1]

while (l>tl&&a[l-1]

while (r

f[l]=f[r]=1;

a[l]=a[r]=x;

c[++t]=1,c1[t]=l,c2[t]=r;

}else{

while (l>tl&&a[l-1]>x) {l--;if (f[l]) l=tl;}

while (rx) {r++;if (f[r]) r=tr;}

f[l]=f[r]=1;

a[l]=a[r]=x;

c[++t]=0,c1[t]=l,c2[t]=r;

}

}

//cout << l << " " << r << endl;

}

e1[i]=l;

e2[i]=r;

}

void solve1(int tt,int tl,int tr,int l,int r){

int x=a[tt];

//cout << x << " " << tl << " " << tr << " " << l << " " << r << endl;

//cout << tl << " " << tr << endl;

while (l>tl||r

//cout << l << " " << r << endl;

if (l>tl){

if (a[l-1]

while (l>tl&&a[l-1]

while (r

f[l]=f[r]=1;

a[l]=a[r]=x;

c[++t]=1,c1[t]=l,c2[t]=r;

}else{

while (l>tl&&a[l-1]>x) {l--;if (f[l]) l=tl;}

while (rx) {r++;if (f[r]) r=tr;}

f[l]=f[r]=1;

a[l]=a[r]=x;

c[++t]=0,c1[t]=l,c2[t]=r;

}

}

//cout << l << " " << r << endl;

if (r

if (a[r+1]

while (l>tl&&a[l-1]

while (r

f[l]=f[r]=1;

a[l]=a[r]=x;

c[++t]=1,c1[t]=l,c2[t]=r;

}else{

while (l>tl&&a[l-1]>x) {l--;if (f[l]) l=tl;}

while (rx) {r++;if (f[r]) r=tr;}

f[l]=f[r]=1;

a[l]=a[r]=x;

c[++t]=0,c1[t]=l,c2[t]=r;

}

}

//cout << l << " " << r << endl;

}

}

void dfs(int x){

if (x>pt) return;

//cout << x << endl;

if (x<=pt&&d2[x]>=d[x+1]-1) {dfs(x+1);solve1(d[x],d1[x],d2[x],e1[x],e2[x]);}

else {solve1(d[x],d1[x],d2[x],e1[x],e2[x]);dfs(x+1);}

}

int main(){

cin >> n;

for (int i = 1; i <= n; i++) cin >> a[i];

for (int i = 1; i <= n; i++) cin >> b[i];

for (int i = 1; i <= n; i++){

if (b[i]!=b[i-1]){

if (i>1) find(b[i-1]);

tl=tr=i;

} else tr++;

}

find(b[n]);

d[pt+1]=n+1;

for (int i = 1; i <= pt; i++) if (i==1) solve(i,1,d[i+1]-1); else solve(i,d[i],d[i+1]-1);

d[1]=1;

//cout << pt << endl;

dfs(1);

cout << t << endl;

for (int i = 1; i <= t; i++){

if (c[i]) cout << "M " << c1[i] << " " << c2[i] << endl;

else cout << "m " << c1[i] << " " << c2[i] << endl;

}

return 0;

}

/*

5

1 5 5 3 4

1 1 4 4 4

5

1 2 3 4 4

2 2 2 2 5

10

7 7 7 7 7 7 3 4 5 6

3 3 3 4 4 4 5 5 5 5

10

1 11 12 13 2 14 15 3 16 17

1 1 1 1 1 1 1 1 2 3

*/

杂事杂项

避免sqrt

权值线段树下去才开，下去才开，传递L，R。

板子整理

1. rng_58 Hash

曼哈顿距离最小生成树 ☆

欧拉距离最小生成树 ☆

k圆并 ☆

k短路 ☆

杜教筛

JAVA与高精度

主席树带修改 ☆

hash板子 9.14-I暴力 ☆

log 质因数分解☆

线性求逆

linux对拍☆

LCT区间加乘 LCT维护子树 LCT维护边权☆

魔法森林 ☆

exlucas+中国剩余定理

SAM

个人训练

团队训练

1. 2018-03-03 Summary 2015 - ICPC - NEERC - Central Subregional

2. 2018-03-04 Summary 2017 - ACM-ICPC Pacific Northwest Regional Contest (Div. 1)

3. 2018-03-09 Summary 2017 - ICPC - Asia - Tsukuba

4. 2018-03-16 Summary Rocky Mountains 2016

5. 2018-03-17 Summary 2018 Zhejiang U Summer Training Camp, Legilimens Contest 1

6. 2018-03-30 Summary Petrozavodsk Winter-2016. JAG Contest

7. 2018-04-05 Summary XVI Open Cup - Grand Prix of Spb

8. 2018-04-13 Summary Petrozavodsk Summer-2017. Warsaw U Contest, XVII OpenCup Onsite

9. 2018-04-20 Summary Makoto Soejima Contest 3 (MIPT Workshop Open 2)

10. 2018-04-22 Summary 2014 - ICPC - Asia - Tokyo

11. 2018-04-27 Summary Petrozavodsk Winter-2018. Carnegie Mellon U Contest

12. 2018-05-11 Summary Moscow Subregional 2014

13. 2018-05-13 Summary XVII Open Cup named after E.V. Pankratiev. Grand Prix of SPb.

14. 2018-05-20 Summary 2015 - XVI Open Cup named after E.V. Pankratiev. GP of Japan.

15. 2018-06-01 Summary 2015 - XVI Open Cup - Grand Prix of Europe (CEPC-2015)

16. 2018-06-08 Summary 2015 - XVI Open Cup named after E.V. Pankratiev. GP of Ukraine

17. 2018-06-10 Summary 2015 - XVI Open Cup named after E.V. Pankratiev. GP of Eurasia

18. 2018-06-15 Summary 2015 - XVI Open Cup named after E.V. Pankratiev. GP of Siberia

19. 2018-08-09 Summary 2017 - ICPC - Europe - SWERC

20. 2018-08-10 Summary 2010 - German Collegiate Programming Contest

21. 2018-08-11 Summary Petrozavodsk Winter-2013. Andrew Stankevich Contest 43

22. 2018-08-12 Summary Petrozavodsk Winter-2013. Andrew Stankevich Contest 43

23. 2018-08-14 Summary 2018 - Multi-University Training - Contest 7 by UESTC

24. 2018-08-15 Summary 2017 - ICPC - Europe - NEERC - Northern Subregional

25. 2018-08-16 Summary 2017 - ICPC - Europe - CERC

26. 2018-08-17 Summary 2014 - Moscow IPT Training Camp - JAG Autumn Contest

27. 2018-08-18 Summary 2014 - ICPC - Europe - NEERC

28. 2018-08-20 Summary 2015 - Moscow International ACM ICPC Workshop - AMPPZ-2015

29. 2018-08-21 Summary 2017 - ICPC - Europe - NEERC

30. 2018-08-22 Summary 2018 - Multi-University Training - Contest 8 by NJU

31. 2018-08-23 Summary 2015 - Moscow International ACM ICPC Workshop - AIM Fund Contest

32. 2018-08-28 Summary 2012-Petrozavodsk Winter. Tokyo Kroliki Contest

33. 2018-08-29 Summary Petrozavodsk Summer-2013. Comenius U Selection by Michal Forisek.

34. 2018-08-25 Summary 2018 - CCPC - Online

35. 2018-09-08 Summary2018 - ICPC - Asia - Shenyang - Online

36. 2018-09-09 Summary2018 - ICPC - Asia - Xuzhou - Online

37. 2018-09-11 SummaryAndrew Stankevich Contest 32 Petrozavodsk Summer Training Camp

38. 2018-09-12 Summary2018 - XVIII Open Cup named after E.V. Pankratiev. Grand Prix of Korea

39. 2018-09-13 Summary Petrozavodsk Winter-2015. Xiaoxu Guo Contest 3.

40. 2018-09-15 Summary 2018 - ICPC - Asia - Jiaozuo - Online

41. 2018-09-16 Summary 2018 - ICPC - Asia - Qingdao - Online

42. 2018-09-19 Summary XVII Open Cup named after E.V. Pankratiev. Grand Prix of Japan.

43. 2018-09-22 Summary - 2018 ICPC Asia Beijing Online

44. 2018-09-24 Summary XVII Open Cup named after E.V. Pankratiev. Eastern Grand Prix.

45. 2018-09-26 Summary Petrozavodsk Summer-2015. Warsaw U Tasks, XV Open Cup Onsite

46. 2018-09-28 Summary 2015 - ICPC - Changchun

47. 2018-09-30 Summary Moscow Pre-Finals Workshop 2016. Kent Nikaido Contest 1

48. 2018-10-01 Summary Petrozavodsk Summer-2013. (ETH Zurich)+ Contest

49. 2018-10-02 Summary Petrozavodsk Winter-2011. Moscow IPT Contest.

50. 2018-10-03 Summary 2013 - 0x11 Ural Championship: Battle of Giants

51. 2018-10-12 Summary 2015 ShenYang Onsite

52. 2018-10-13 Summary 2016 ccpc hefei

53. 2018-10-17 Summary 2015-2016 Petrozavodsk Winter Training Camp, Makoto rng_58 Soejima Сontest 4

54. 2018-10-19 Summary 2017 shenyang ICPC

55. 2018-10-24 Summary 2016-17 NTU WF Selecting Contest

56. 2018-11-03 Summary 2015 - ICPC - EC FINAL

57. 2018-11-09 Summary XIV Open Cup named after E.V. Pankratiev. GP of America.

58. 2018-11-10 Summary XVI Open Cup named after E.V. Pankratiev. GP of Ekaterinburg.

58. 2018-11-13 Summary2017-2018 ACM-ICPC German Collegiate Programming Contest (GCPC 2017)

= 比赛记录 ==

1. 2018-04-07 Summary - 2018 ZJUPC

2. 2018-04-29 Summary - 2018 ZJPC

3. 2018-10-21 Summary - 2018 ACM/ICPC ShenYang Onsite

4. 2018-10-21 Summary - 2018 CCPC Guilin Onsite

补题

Contest Name A B C D E F G H I J K L M
2015 - ICPC - NEERC - Central Subregional O O Ø O # . Ø O O O O X X
2017 - ACM-ICPC Pacific Northwest Regional Contest (Div. 1) O . O Ø O Ø O Ø . O . O O
2017 - ICPC - Asia - Tsukuba O O O . Ø O . Ø O Ø Ø X X
Rocky Mountains 2016 O O O O O O O O O O X X X
2018 Zhejiang U Summer Training Camp, Legilimens Contest 1 O O O . Ø O . . O O O X X
Petrozavodsk Winter-2016. JAG Contest O O O O O Ø Ø O . .. Ø X X
XVI Open Cup - Grand Prix of Spb O . . O O . . O O O . . X
2018 ZJUPC O . O O . O O O . O X X X
Petrozavodsk Summer-2017. Warsaw U Contest, XVII OpenCup Onsite Ø Ø O O . . O O . O O X X
Makoto Soejima Contest 3 (MIPT Workshop Open 2) Ø O Ø Ø Ø . O O . . . X X
2014 - ICPC - Asia - Tokyo O O O O O O O . Ø . . X X
Petrozavodsk Winter-2018. Carnegie Mellon U Contest Ø O Ø Ø . O . O Ø Ø . X X
2018 ZJPC O O # O O O . . O O O O O
Moscow Subregional 2014 O Ø O O O O O Ø Ø . . . X
XVII Open Cup named after E.V. Pankratiev. Grand Prix of SPb. O O . O O O O O . .. O X X
2015 - XVI Open Cup named after E.V. Pankratiev. GP of Japan. O O . O . O O Ø Ø Ø X X X
2015 - XVI Open Cup - Grand Prix of Europe (CEPC-2015) O O . O Ø Ø . O Ø Ø O . X
2015 - XVI Open Cup named after E.V. Pankratiev. GP of Ukraine O O O O Ø O O . . . O . O
2015 - XVI Open Cup named after E.V. Pankratiev. GP of Eurasia O O O O O O . O O . O Ø X
2015 - XVI Open Cup named after E.V. Pankratiev. GP of Siberia O O O O O . Ø O . O O . X
2017 - ICPC - Europe - SWERC O O O # O O O . . O O X X
2017 - ICPC - Europe - NEERC - Moscow Subregional O . O O . O O O . . . X X
Petrozavodsk Winter-2013. Andrew Stankevich Contest 43 . O . # . . . O O O O O X
2018 - Multi-University Training - Contest 7 by UESTC Ø . . . O Ø . Ø O O O X X
2017 - ICPC - Europe - NEERC - Northern Subregional O O O . O . O O O . O O X
2017 - ICPC - Europe - CERC O . . . . O . O . O . O X
2014 - Moscow IPT Training Camp - JAG Autumn Contest O O . O . Ø O . . O O X X
2014 - ICPC - Europe - NEERC O O . Ø Ø O . . O O O X X
2015 - Moscow International ACM ICPC Workshop - AMPPZ-2015 Ø # . O . O . Ø O . . Ø X
2017 - ICPC - Europe - NEERC O O O O O Ø . . . . . # X
2018 - Multi-University Training - Contest 8 by NJU O O . O O . . . . O . Ø X
2015 - Moscow International ACM ICPC Workshop - AIM Fund Contest O # # . O Ø O O O O # X X
2012 - Petrozavodsk Winter. Tokyo Kroliki Contest . # O O . . O O . O . X X
Petrozavodsk Summer-2013. Comenius U Selection by Michal Forisek. O O # . O O O . X X X X X
2018 - CCPC - Online O . O O O . O . O O X X X
2018 - ICPC - Asia - Shenyang - Online . . O O O O O . O Ø O X X
2018 - ICPC - Asia - Xuzhou - Online O O O Ø # O O O O O O X X
Andrew Stankevich Contest 32 Petrozavodsk Summer Training Camp O O O O Ø O O . . Ø O X X
2018 - XVIII Open Cup named after E.V. Pankratiev. Grand Prix of Korea Ø . O O . O . . . . . Ø X
Petrozavodsk Winter-2015. Xiaoxu Guo Contest 3. Ø O . . O Ø O . Ø O X X X
2018 - ICPC - Asia - Jiaozuo - Online O O . Ø O O O O O O O X X
2018 - ICPC - Asia - Qingdao - Online O # O # . Ø O . . O O X X
XVII Open Cup named after E.V. Pankratiev. Grand Prix of Japan. . . . O . . . O . . X X X
2018 ICPC Asia Beijing Online O O O O . . . O . . X X X
XVII Open Cup named after E.V. Pankratiev. Eastern Grand Prix. O O . O O O O O O . . O X
Petrozavodsk Summer-2015. Warsaw U Tasks, XV Open Cup Onsite . O # . O . . O O . . X X
2015 - ICPC - Changchun Ø O . . O O O O . O . O X
Moscow Pre-Finals Workshop 2016. Kent Nikaido Contest 1 O . . O . . . O . O O X X
Petrozavodsk Summer-2013. (ETH Zurich)+ Contest O O O . . O . O O O . O X
0x11 Ural Championship: Battle of Giants. O O . . O . . O O O . . X
2015 ShenYang Onsite . O . O . . Ø . O . . . O
2016 ccpc hefei O . O O O . Ø O O Ø X X X
2015-2016 Petrozavodsk Winter Training Camp, Makoto rng_58 Soejima Сontest4 . O O . O # . . # O . O .
2017 shenyang ICPC . . O . . O . . O . O O O
2018 ACM/ICPC ShenYang Onsite . . O . O . O . . O . O .
2016-17 NTU WF Selecting Contest O Ø O . . . O . Ø O . . .
2018 CCPC Guilin Onsite Ø . . O . . O O . O . O X
2015 - ICPC - EC FINAL O O . O . O . . . O . O O
XIV Open Cup named after E.V. Pankratiev. GP of America. O . O O . . O O O O X X X
XVI Open Cup named after E.V. Pankratiev. GP of Ekaterinburg. . O O O O O O . . O . X X
2017-2018 ACM-ICPC German Collegiate Programming Contest (GCPC 2017) Ø O O O O O O Ø O O O X X

O:当场通过 .:尚未通过 Ø:赛后通过 #:口胡通过 X:不存在的 ..:想去补的没过题留个标记……

附加文件