[CF 487D] Conveyor Belts

作法：

因為他的輸送帶的方向只有左右上，所以分塊顯然可以做，只是複雜度有點高。官方解中提到的線段樹的作法沒有寫的很清楚，這裡詳細講一下。

假設線段樹的某個節點的區間為$[L,R]$，則這個節點裡放的資訊為：考慮$(L,1),(R,m)$形成的矩形，則從每個$x$座標為$R$的格子開始走，走出這塊矩形時的第一個格子是哪格，或是會形成無窮回圈。也就是這個節點裡存了$m$個格子的座標（所以是$m$個pair）。那麼就可以由$[a,b]$和$[b+1,c]$的資訊推出$[a,c]$的資訊了，因此可以用線段樹把每個節點的資訊都先處理好。至於如何回答詢問，假設詢問的點為$(x,y)$首先把線段$[1,x]$用線段樹拆解成好幾個線段，那麼只要從最後一個拆出來線段開始，利用線段樹上已經處理好的資訊就可以直接跳到下一個線段的起點$x$座標，或是得知他會走出左右邊界，或是形成無窮回圈了。而修改是顯然的。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10,maxm=10+2 ;
 
struct P{int x,y;}ST[4*maxn][maxm];
char G[maxn][maxm] ;
int n,m ;
 
void cal(int x,P *a)
{
    for(int i=1;i<=m;i++)
        a[i]=(G[x][i]=='^' ? (P){x-1,i} : (P){-2,-2}) ;
    if(G[x][1]=='<') a[1]=(P){x,0} ;
    if(G[x][m]=='>') a[m]=(P){x,m+1} ;
    for(int i=1;i<m;i++) if(G[x][i]=='>' && G[x][i+1]=='<')
        a[i]=a[i+1]=(P){-1,-1} ;
    for(int i=1;i<=m;i++) if(G[x][i]=='<' && a[i].x==-2)
        a[i]=a[i-1] ;
    for(int i=m;i>=1;i--) if(G[x][i]=='>' && a[i].x==-2)
        a[i]=a[i+1] ;
}
 
void pull(int l,int r,P *a,P *b,P *c)
{
    int mid=(l+r)/2 ;
    for(int i=1;i<=m;i++)
        c[i]=(b[i].x==mid ? a[b[i].y] : b[i]) ;
}
 
void build(int l,int r,int id)
{
    if(l==r){cal(l,ST[id]) ; return ;}
    int mid=(l+r)/2 ;
    build(l,mid,2*id) ;
    build(mid+1,r,2*id+1) ;
    pull(l,r,ST[2*id],ST[2*id+1],ST[id]) ;
}
 
void modify(int l,int r,int id,int pos)
{
    if(l==r){cal(l,ST[id]) ; return ;}
    int mid=(l+r)/2 ;
    if(pos<=mid) modify(l,mid,2*id,pos) ;
    else modify(mid+1,r,2*id+1,pos) ;
    pull(l,r,ST[2*id],ST[2*id+1],ST[id]) ;
}
 
struct Q{int l,r,id;};
vector<Q> v ;
void getseg(int l,int r,int L,int R,int id)
{
    if(l==L && r==R){v.push_back((Q){L,R,id}) ; return ;}
    int mid=(L+R)/2 ;
    if(r<=mid) getseg(l,r,L,mid,2*id) ;
    else if(l>mid) getseg(l,r,mid+1,R,2*id+1) ;
    else getseg(l,mid,L,mid,2*id) ,
        getseg(mid+1,r,mid+1,R,2*id+1) ;
}
 
main()
{
    int q ; scanf("%d%d%d",&n,&m,&q) ;
    for(int i=1;i<=n;i++) scanf("%s",G[i]+1) ;
    build(1,n,1) ;
    while(q--)
    {
        int x,y ;
        char c[3] ; scanf("%s%d%d",c,&x,&y) ;
        if(c[0]=='C')
        {
            scanf("%s",c) ;
            G[x][y]=c[0] ;
            modify(1,n,1,x) ;
        }
        else
        {
            v.clear() ;
            getseg(1,x,1,n,1) ;
            reverse(v.begin(),v.end()) ;
            P now=(P){x,y} ;
            for(auto i : v)
            {
                now=ST[i.id][now.y] ;
                if(now.x != i.l-1) break ;
            }
            printf("%d %d\n",now.x,now.y) ;
        }
    }
}