超超超超超爽的一道题！

· · 题解

这题啊……真的是无话可说了，做完浑身舒畅的那种。

我们先不考虑 corner case。

首先肯定是按套路假设一轮过完之后起点移动的向量是 (dx,dy)。

我们考虑每一次的到达的点其实是很有规律的，对应点坐标之间会恰好差一个 (dx,dy)。那我们不难想到给它取模一下（不妨 dx>0）。

具体来说，我们用 (x,y,t) 来表示 (x+t\times dx,y+t\times dy)，同时要求 x\in[0,dx)。

这样的话，我们如果先暴力走一轮，那么对于一个走到的点 (x,y,r)（注意这里 r 不一定等于 0，因为有可能走到 dx 外面去），我们实际上能走到的点是 (x,y,r),(x,y,r+1),\cdots,(x,y,r+k-1)，这本身是一个很好看的区间形式。注意起始点要特判一下，不过这不重要。

那么我们考虑正方形的四个顶点。我们会发现，如果对于一个 r，这四个点的前两维坐标都是合法的，那么就会产生 1 的贡献。那么我们不妨换它一下，枚举四个顶点的前两维坐标（实际上只会有线性个这样的坐标，因为它们一定都在第一轮中出现过），然后考虑它们出现的位置（一定分别是若干个区间的并，这个开始扫一遍就可以搞定）的交，这玩意就很好处理了，来挑战这道题的人想必都会。注意有可能比如枚举左下角的时候发现另外三个点里有点的 x 坐标达到了 dx，那没有关系，还是先转换成我们的标准坐标形式，对搞出来的范围平移一下就好了。

接下来是一些 corner case。

  1. dx<0

把所有 E 和 W 交换就好了。

  1. dx=0,dy\not=0

把 dx 和 dy 交换一下就好了。有可能需要用上面第一种情况额外处理一下。

  1. dx=dy=0

每一轮都一样，走一轮就好了。可以把 dx 手动改成充分大来回避其他问题。

代码（采用的区间是左闭右开的）：

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>itv;
int dx,dy;
map<itv,set<itv>>cnt;
void init(){
    int n,k;
    string s;
    cin>>n>>k>>s;
    auto op=[](int&x,int&y,char c){
        switch(c){
            case 'E':++x;break;
            case 'N':++y;break;
            case 'W':--x;break;
            case 'S':--y;break;
        }
    };
    for(char c:s)op(dx,dy,c);
    auto trans=[&s](vector<pair<char,char>>trs){
        for(char&c:s)
            for(auto[c1,c2]:trs)
                if(c==c1)c=c2;
                else if(c==c2)c=c1;
    };
    if(!dx){
        swap(dx,dy),trans({{'E','N'},{'W','S'}});
        if(!dx)dx=250637,k=1;
    }
    if(dx<0)dx=-dx,trans({{'E','W'}});
    auto ins=[](itv pos,itv val){
        auto&st=cnt[pos];
        auto itl=st.lower_bound({val.first,INT_MIN});
        if(itl!=st.begin()&&prev(itl)->second>=val.first)--itl;
        auto itr=st.upper_bound({val.second,INT_MAX});
        if(itl==itr)st.insert(val);
        else{
            int l=min(itl->first,val.first),r=max(prev(itr)->second,val.second);
            st.erase(itl,itr),st.emplace(l,r);
        }
    };
    ins({0,0},{0,1});
    for(int x=0,y=0;char c:s){
        op(x,y,c);
        int dt=x/dx,px=x-dt*dx,py=y-dt*dy;
        if(px<0)px+=dx,py+=dy,--dt;
        ins({px,py},{dt,k+dt});
    }
}
signed main(){
    long long ans=0;
    auto atval=[](int x,int y){
        vector<itv>ret;
        int dt=0;
        if(x==dx)x-=dx,y-=dy,dt=1;
        if(auto it=cnt.find({x,y});it!=cnt.end()){
            ret.reserve(it->second.size());
            copy(it->second.begin(),it->second.end(),back_inserter(ret));
            for(auto&[l,r]:ret)l-=dt,r-=dt;
        }
        return ret;
    };
    auto merge=[](auto x,auto y){
        vector<itv>ret;
        for(auto pos=y.begin();auto[l,r]:x)
            while(pos!=y.end()){
                while(pos!=y.end()&&pos->second<=l)++pos;
                if(pos==y.end()||pos->first>=r)break;
                ret.emplace_back(max(l,pos->first),min(r,pos->second));
                if(pos->second>=r)break;
                else ++pos;
            }
        return ret;
    };
    for(init();auto[pos,iv]:cnt){
        auto[x,y]=pos;
        for(auto[l,r]:merge(merge(atval(x,y),atval(x+1,y+1)),merge(atval(x+1,y),atval(x,y+1))))
            ans+=r-l;
    }
    return cout<<ans<<endl,0;
}