题解：P5102 [JOI 2016 Final] 领地 / Territory

· · 题解

C.P5102 [JOI 2016 Final] 领地 / Territory - 洛谷

题意：你会按照指令上下左右走，时限可以完整模拟一轮，但是需要重复走 K 轮，求走过的点中间有多少个 1\times1 的正方形（正方形四个点都被走过）。

很好的题目喵喵喵！

考虑完整的一轮后你到达的终点 (x,y)，发现这是一个偏移量，每次相当于你走的路经偏移 (?+x,?+y) 后得到的路径，k 次偏移后求一个并。

就类似于这样偏移此时 K=5。

考虑把第一次操作暴力模拟一遍，记录 f_{t,i,j} 表示现在已经偏移了 t 个 (x,y) 了，偏移回来对应的位置在 (i,j)。你此时就会像我一样，惊奇地发现每个操作后的这个f 的 t 在 k 次后恰好对应着一段区间！！！但是一个位置的 t 并非如此，例子：由于第一次走过了f_{0,i,j},f_{4,i,j}，钦定 K=2，那么最终 (i,j) 这个点覆盖的 t 就是 [0,1],[4,5]。但是发现一个区间对应一个操作，初始的一轮完整操作的复杂度是可以接受的，所以你可以直接枚举操作经过的 (i,j) 这个也只有 O(n) 个。每次，直接枚举以它为左下角的正方形四个位置对应的区间暴力求交复杂度就是正确的，在边界需要特判一下 t,(n-1,m-1)，对应的右上端点应该是 t+1,(0,0)。偏移量 n=0 就把 n,m 交换一下，都是 0 进行 1 轮即可。最终时间复杂度 O(n\log n)。

Code：太阳只有一个，却遍地都是阳光，相信未来时光明的。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
int dx,dy;
map<pii,set<pii>>mp;

int n,k,ans;

string s; 

void p(char c,int& dx,int&dy){
    if(c=='E')++dx;if(c=='N')++dy;
    if(c=='W')--dx;if(c=='S')--dy;
}

void cha(pii x,pii w){
    auto&s=mp[x];
    auto l=s.lower_bound({w.fi,-2e9});
    if(l!=s.begin()&&prev(l)->se>=w.fi)l--;
    auto r=s.upper_bound({w.se,2e9});
    if(l==r)s.insert(w);
    else{
        int l1=min(l->fi,w.fi),r1=max(prev(r)->se,w.se);
        s.erase(l,r),s.emplace(l1,r1);
    }
}

auto get(int x,int y){
    vector<pii> v;
    int t=0;if(x==dx)x-=dx,y-=dy,t=1;
    auto it=mp.find({x,y});
    if(it!=mp.end()){
        v.reserve(it->se.size());
        copy(it->second.begin(),it->second.end(),back_inserter(v));
        for(auto&[l,r]:v)l-=t,r-=t;
    }
    return v;
}

auto he(auto x,auto y){
    vector<pii> v;
    for(auto it=y.begin();auto [l,r]:x){
        while(it!=y.end()){
            while(it!=y.end()&&it->se<=l)it++;
            if(it==y.end()||it->fi>=r)break;
            v.push_back({max(it->fi,l),min(r,it->se)});
            if(it->se>=r)break;
            else it++;
        }
    }
    return v;
}

signed main(){
    cin>>n>>k>>s;
    for(char c:s){
        p(c,dx,dy);
    }
    if(!dx){
        swap(dx,dy);for(char&c:s){
            if(c=='E')c='N';
            else if(c=='N')c='E';
            if(c=='W')c='S';
            else if(c=='S')c='W';
        }
        if(!dx)dx=114514,k=1;
    }
    if(dx<0){dx=-dx;for(char&c:s)if(c=='E')c='W';else if(c=='W')c='E';}
    int x=0,y=0;
    cha({0,0},{0,1});//左闭右开 
    for(char c:s){
        p(c,x,y);
        int t=x/dx,px=x-t*dx,py=y-t*dy;
        if(px<0)t--,px+=dx,py+=dy;
        cha({px,py},{t,t+k}); 
    }
    for(auto [p,v]:mp){
        auto[x,y]=p;
        for(auto[l,r]:he(he(get(x,y),get(x+1,y+1)),he(get(x,y+1),get(x+1,y))))
        ans+=r-l;
    }
    cout<<ans;
    return 0;
}