UNR #1 题解

A. 争夺圣杯

还是想说一下，这题是原题啊...想做的人可以戳codechef上的MTMXSUM（懒得贴链接了，套了个壳，不过正常人应该都能看得出来）

显然异或输出没什么奇怪的性质...

考虑一个元素a[x]在哪些区间中会成为最大值，我们可以用单调栈找出前面比这个元素大的第一个元素a[l]，右边大的第一个元素a[r]。

考虑这个元素对每一长度的贡献，设p=x-l，q=r-x，那么对于区间[s,t]，只有当l<s<=x，x<=t<r，只有这pq个区间最大值为a[x]。

那么考虑这些区间的长度，不妨设p<=q，那么可以根据区间长度跟p、q的关系来统计答案。

当1<=len<=p时，显然共有len个区间（因为x肯定要在区间内）。

当p<len<=q时，共有p个区间（因为左端点可以是l+1~x）

当q<len<=p+q-1时，共有p+q-len个（[x-p+1,x-p+len]...[x+q-len,x+q-1]）

好像是个区间加等差数列，随便前缀和维护一下。

具体地，例如[p,q]加1...q-p+1，这种事情我们用两个数组s1,s2来维护，s1[p...q]+=1，s2[p...q]-=p-1，这个前缀和搞搞。最后我们只要统计s1*i+s2就行了。

实现时l和r需要一边开一边闭（一边大于，一边大于等于），然后用单调栈维护即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll MOD=998244353;
#define SZ 2333333
int n; ll hh[SZ];
#define gc getchar()
int gi_()
{
    int s,c;
    while(c=gc,c<48||c>57);
    s=c-48;
    while(c=gc,c>=48&&c<=57) s=s*10+c-48;
    return s;
}
#define gi gi_()
int L[SZ],R[SZ],ss[SZ],sn=0;
ll q1[SZ],q2[SZ];
void add(ll& a,ll b)
{
    a+=b; a%=MOD;
    if(a<0) a+=MOD;
}
int main()
{
    n=gi;
    for(int i=1;i<=n;i++) hh[i]=gi;
    for(int i=1;i<=n;i++)
    {
        while(sn&&hh[ss[sn]]<hh[i]) --sn;
        if(sn) L[i]=ss[sn]; ss[++sn]=i;
    }
    sn=0;
    for(int i=n;i>=1;i--)
    {
        while(sn&&hh[ss[sn]]<=hh[i]) --sn;
        if(sn) R[i]=ss[sn]; else R[i]=n+1;
        ss[++sn]=i;
    }
    for(int i=1;i<=n;i++) hh[i]%=MOD;
    for(int i=1;i<=n;i++)
    {
        int l=L[i],r=R[i];
        //1,min(i-l,r-i),max(i-l,r-i),(r-l)
        add(q1[1],hh[i]); add(q1[min(i-l,r-i)],-hh[i]);
        add(q2[min(i-l,r-i)],min(i-l,r-i)*(ll)hh[i]%MOD);
        add(q2[max(i-l,r-i)],(r-l)*(ll)hh[i]%MOD-min(i-l,r-i)*(ll)hh[i]%MOD);
        add(q2[r-l],-(r-l)*(ll)hh[i]%MOD);
        add(q1[max(i-l,r-i)],-hh[i]); add(q1[r-l],hh[i]);
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        add(q1[i],q1[i-1]); add(q2[i],q2[i-1]);
        ll orz=((q1[i]*i%MOD+q2[i]%MOD)%MOD+MOD)%MOD;
        ans^=orz;
    }
    printf("%d
",ans);
}

C. 果冻运输

好好的一道人类智慧提答（确实很好玩）硬生生搞成了暴搜题...

开始我写了个暴力，看看数据范围，心想：肯定搜不出来，就只写了个iddfs，然后把状态hash一下输出，目测找一找规律...

最后有几个点目测玩到了一些两三分的acceptable answer...其他点都搜出1分左右...旁边wwf大爷玩了5h提答，看起来过了十几个点，结果交上去都是两三分，结果总分还没我一堆1分高...惨啊

Q：没想到A*吗？

A：想啦，感觉估价函数非常蛋疼...谁知道设成同色联通块个数这种辣鸡玩意儿就行了...

Q：那也比傻逼暴搜好啊

A：惨啊

人类智慧做法可戳：http://dram.blog.uoj.ac/blog/1864（当然不是我写的

A*大法可戳：http://immortalco.blog.uoj.ac/blog/1854

有空去写写把...

A. Jakarta Skyscrapers

大意就是有一个集合，里面可以容纳正整数。开始里面只有a和b两个正整数，对于集合中两个数x和y，可以通过一次操作得到x-y并插入到集合中。（注意到集合中只能有正整数，所以必须x>=y）。求一些操作使得集合中包含正整数c。输出任意一种步数小于400的方案，如果不存在输出-1。

显然400步内不存在，那么肯定也不存在解了...

然后我们写个暴力，可以发现，A>=B时当且仅当C<=A且gcd(A,B)|C才有解，所以我们就可以判出-1。

（以下内容与题解一点关系都没有）

然后我们发现gcd不是这么写吗：

ll gcd(ll a,ll b)
{
    while(b)
    {
        ll t=a%b; a=b; b=t;
    }
    return a;
}

那么假如我们自己实现了什么方法，能高效地在这个系统中实现取模和乘法，那么我们就这样做gcd，最后乘上C/gcd(A,B)就做完了。

接下来我们就说说怎么做吧。

减法：有啦 1次

加法：注意到A-(A-x-y)=x+y。 3次

乘法：注意到我们可以快速加 O(log)次

取模：被除数-商*除数 O(log)次

那么gcd的复杂度：

复杂度似乎挺科学？可是我这样写完只有70...看到一个点403次简直哭瞎。

后面用个map加了点记忆化就行啦。求hack

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <map>
using namespace std;
typedef long long ll;
#define SZ 666666
ll A,B,C,la[SZ],lb[SZ];
int ls=0;
map<ll,bool> qd;
//O(1)
ll gminus(ll a,ll b)
{
    if(!b) return a;
    if(a==b) return 0;
    if(qd[a-b]) return a-b;
    qd[a-b]=1;
    ++ls; la[ls]=a; lb[ls]=b;
    return a-b;
}
//O(3)
ll gadd(ll a,ll b)
{
    if(a+b>=A) return A;
    if(qd[a+b]) return a+b;
    gminus(A,a);
    gminus(A-a,b);
    gminus(A,A-a-b);
    return a+b;
}
ll ss[233333];
//O(log)
//不需要b在集合中 
ll gmul(ll a,ll b)
{
    if(qd[a*b]) return a*b;
    ll tg=a*b;
    ll cur=A,sn=0;
    while(b)
    {
        if(b&1)
        {
            for(int i=1;i<=sn;i++) gadd(ss[i],ss[i]); sn=0;
            cur=gminus(cur,a);
            if(qd[tg-(A-cur)]) return gadd(tg-(A-cur),gminus(A,cur));
        }
        ss[++sn]=a; a<<=1; b>>=1;
    }
    return gminus(A,cur);
}
//O(log)
ll gmod(ll a,ll b)
{
    if(a%b==0) return 0;
    if(qd[a%b]) return a%b;
    return gminus(a,gmul(b,a/b));
}
ll gcd(ll a,ll b)
{
    while(b)
    {
        ll t=a%b; a=b; b=t;
    }
    return a;
}
void ggcd(ll a,ll b)
{
    while(b)
    {
        ll t=gmod(a,b); a=b; b=t;
    }
}
int main()
{
    cin>>A>>B>>C; qd[A]=qd[B]=1;
    if(A<B) swap(A,B);
    if(C%gcd(A,B)!=0||C>A) {puts("-1"); return 0;}
    ll gcdd=gcd(A,B);
    ggcd(A,B);
    gmul(gcdd,C/gcdd);
    cout<<ls<<"
";
    for(int i=1;i<=ls;i++) cout<<la[i]<<" "<<lb[i]<<"
";
}

C. 火车管理

建议不要用题解的做法，高级做法参见 http://wangyisong1996.blog.uoj.ac/blog/1866 （人傻看不懂官方题解

感觉说的十分清楚啊（虽然我也看不懂复杂度分析

两个傻逼错误一个调了一小时，一个调了两小时...大概就是标记到了叶子还往下pushdown标记就失踪了...

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <time.h>
#include <stdlib.h>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
#include <sstream>
#include <stack>
#include <iomanip>
using namespace std;
#define pb push_back
#define inf 1001001001
#define infll 1001001001001001001LL
#define FOR0(i,n) for(int (i)=0;(i)<(n);++(i))
#define FOR1(i,n) for(int (i)=1;(i)<=(n);++(i))
#define mp make_pair
#define pii pair<int,int>
#define ll long long
#define ld double
#define vi vector<int>
#define fi first
#define se second
#define SZ 1048588
#define S2 SZ*65
int an=0,lc1[S2],rc1[S2],vs[S2];
int newn(int x) {return vs[++an]=x, an;}
int join(int a,int b)
{
    //cout<<"JOIN"<<a<<","<<b<<"
";
    if(a&&b);else return a^b;
    int s=newn(vs[a]);
    lc1[s]=a; rc1[s]=b;
    return s;
}
int delf(int x)
{
    if(!x||!lc1[x]) return 0;
    else if(lc1[lc1[x]])
    {
        int g=++an;
        lc1[g]=delf(lc1[x]);
        rc1[g]=rc1[x];
        vs[g]=vs[lc1[g]];
        return g;
    }
    else return rc1[x];
}
int ls[SZ],rs[SZ],sum[SZ],tag[SZ],M=524288,M2=M+M;
void tagit(int x,int vid)
{
    if(!x||x>M2) return;
    sum[x]=(rs[x]-ls[x]+1)*vs[vid];
    tag[x]=join(vid,tag[x]); //md这一句调了我一个小时 
}
void pd(int x)
{
    if(!x||x>M2||!tag[x]||x+x>M2/*wtf*/) return;
    tagit(x+x,tag[x]);
    tagit(x+x+1,tag[x]);
    tag[x]=0;
}
void upd(int x)
{
    //pd(x+x); pd(x+x+1);
    sum[x]=sum[x+x]+sum[x+x+1];
}
void popt(int x)
{
    if(!x||x>M2||!tag[x]) return;
    sum[x]-=vs[tag[x]];
    tag[x]=delf(tag[x]);
    if(tag[x]) sum[x]+=vs[tag[x]];
}
void build()
{
    for(int i=1;i<=M;i++) ls[i+M]=rs[i+M]=i;
    for(int i=M-1;i>=1;i--) ls[i]=ls[i+i], rs[i]=rs[i+i+1];
}
void push(int x,int l,int r,int ns)
{
    if(l>r||!x||x>M2) return;
    if(ls[x]==l&&rs[x]==r) {tagit(x,ns); return;}
    pd(x);
    int m=ls[x]+rs[x]>>1;
    push(x+x,l,min(r,m),ns);
    push(x+x+1,max(m+1,l),r,ns);
    upd(x);
}
void pop(int x,int p)
{
    if(!x||x>M2||p<ls[x]||p>rs[x]) return;
    if(ls[x]==rs[x]) {popt(x); return;}
    pd(x); pop(x+x,p); pop(x+x+1,p); upd(x);
}
int query(int x,int l,int r)
{
    if(l>r||!x||x>M2) return 0;
    if(ls[x]==l&&rs[x]==r) return sum[x];
    pd(x);
    int m=ls[x]+rs[x]>>1,ans=0;
    ans+=query(x+x,l,min(r,m));
    ans+=query(x+x+1,max(m+1,l),r);
    upd(x);
    return ans;
}
int main()
{
    build();
    int n,m,ty,lans=0;
    scanf("%d%d%d",&n,&m,&ty);
    while(m--)
    {
        int tp,a,b,c;
        scanf("%d",&tp);
        if(tp!=2)
        {
            scanf("%d%d",&a,&b);
            a=(a+lans*ty)%n+1; b=(b+lans*ty)%n+1;
            if(a>b) swap(a,b);
        }
        else
        {
            scanf("%d",&a);
            a=(a+lans*ty)%n+1;
        }
        if(tp==1) printf("%d
",lans=query(1,a,b));
        else if(tp==2) pop(1,a);
        else scanf("%d",&c), push(1,a,b,newn(c));
        //if(m&127);else cerr<<m<<"
";
    }
}

最后似乎是rank40卡线银牌？反正涨了很多rating还是很高兴的（因为之前rating太低辣）

剩下的题解等看懂了再来补...