[TIOJ 1869] 堆石子遊戲

原題：http://tioj.ck.tp.edu.tw/problems/1869
AC：http://tioj.ck.tp.edu.tw/submissions/25991

解題方向：二維BIT，分塊


題目大意：平面點修改值，平面查詢總和。

解法：二維BIT可以在$O(Q\log^2N)$輕鬆過這一題，如果要練$\sqrt N$分塊的話也是可以。

#include<bits/stdc++.h>
using namespace std;
int bbit[1025][1025];
int N;
inline void add(int v,int x,int y)
{
    while( x <= N )
    {
        for(int j=y;j<=N;j+=j&-j)
            bbit[x][j]+=v;
        x+=x&-x;
    }
}
inline int sum(int x,int y)
{
    int ans = 0;
    while( x )
    {        
        for(int j=y;j;j-=j&-j)
            ans+=bbit[x][j];
        x-=x&-x;
    }
    return ans;
}
int main()
{
    cin>>N;
    int mod,x1,y1,x2,y2,v;
    while(cin>>mod)
    {
        if( mod == 1 )
        {
            cin>>x1>>y1>>v;
            x1++;y1++;
            add(v,x1,y1);
        }
        else
        {
            cin>>x1>>y1>>x2>>y2;
            x1++;y1++;x2++;y2++;
            cout<< sum(x2,y2) - sum(x1-1,y2) - sum(x2,y1-1)+sum(x1-1,y1-1) <<'\n';
        }
    }
}

[TIOJ 1603] 胖胖殺蚯事件

原題：http://tioj.ck.tp.edu.tw/problems/1603
AC：http://tioj.ck.tp.edu.tw/submissions/17785

解題方向：RMQ


題目大意：區間最大值減最小值

解法：RMQ裸題，沒有修改，所以想要線段樹、Treap、莫對、塊狀練表等等做一做就會AC了，可以拿來實驗很多新方法的題目XD。這裡使用的是Sparse Table，因為沒有修改，顯得特別有優勢。

看到學弟最近在寫這題，無聊來刷了一下Rank~

列舉各方法複雜度

方法	建構資料	查詢	備註
Sparse Table	$n\log n$	$1$	黑魔法加持
線段樹	$n\log n$	$\log n$
樹堆	$n\log n$	$\log n$	常數大
莫對數組	$n\log n+n\sqrt{n}$	$1$
塊狀鍊表	$n\sqrt{n}$	$\sqrt{n}$

學高級技巧時，也別忘了最單純的想法

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

typedef long long ll;
ll spM[17][100001];
ll spm[17][100001];
int main()
{
    #ifdef DBG
    //freopen("case.in", "r" , stdin);
    #endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int N,Q,gap,jmp;
    cin>>N>>Q;
    for(int i=1;i<=N;++i)
    {
        cin>>spM[0][i];
        spm[0][i]=spM[0][i];
    }
    for(int i=1; (1<<i)<=N; ++i )
    {
        jmp = ( 1<<(i-1) );
        for(int j=1; j+jmp<=N; ++j )
        {
            spM[i][j] = max( spM[i-1][j] , spM[i-1][j+jmp] ); 
            spm[i][j] = min( spm[i-1][j] , spm[i-1][j+jmp] );
        }
    }
    while(Q--)
    {
        int L,R;
        cin>>L>>R;
        gap = 31 - __builtin_clz(abs(L-R)+1);
        cout<< max( spM[gap][L],spM[gap][R-(1<<gap)+1] )
              -min( spm[gap][L],spm[gap][R-(1<<gap)+1] ) << '\n';
    }
}

同場加映線段樹

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
pii data[400000];
pii merge(const pii &a,const pii &b)
{
    return { min(a.first,b.first) , max(a.second,b.second) };
}

void update(int i,ll v,int L,int R,int I)
{
    if(L==R){
        data[I]={v,v};
        return ;
    }
    int M = (L+R)/2;
    if(i<=M)update(i,v,L,M,I*2+1);
    else update(i,v,M+1,R,I*2+2);
    data[I] = merge(data[I*2+1],data[I*2+2]);
}

pii find(int l,int r,int L,int R,int I)
{
    if( L==l && R==r ) return data[I];
    int M = (L+R)/2;
    if ( r<=M ) return find(l,r,L  ,M,I*2+1);
    if ( M< l ) return find(l,r,M+1,R,I*2+2);
    return merge(   find(l  ,M,L  ,M,I*2+1),
                    find(M+1,r,M+1,R,I*2+2));
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N,M,a,b;
    ll t;
    cin>>N>>M;
    for(int i=1;i<=N;++i)
    {
        cin>>t;
        update(i,t,1,N,0);
    }
    while(M--)
    {
        cin>>a>>b;
        auto p = find(a,b,1,N,0);
        cout<<p.second-p.first<<'\n';
    }
    return 0;
}

[TIOJ 1396] 線段覆蓋

原題：http://tioj.ck.tp.edu.tw/problems/1396
AC：http://tioj.ck.tp.edu.tw/submissions/17674

解題方向：單調性，貪心法


題目大意：兩個人分別有不同的兩組線段，有標記放置的位置，試問誰能用最少的線段覆蓋指定區間。

解法：我們可以分開計算兩個人所需的線段，把線段排序後，由左向右掃描，檢查最右界是否能到達終點即可。

本方法最費時間的為排序，總複雜度為$O(n\log n)$

透過特判可以把時間壓到$140ms$，不過$visitorIKC$的$61ms$我還沒頭緒，是不是能在優化到線性複雜度呢? (對方表示他只是極致的壓常數

#include<bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    pair<int,int> d[2][100000];
    int N[2];
    int X,Y;
    int ans[2];
    register int i,j,mx,ed;
    bool flag;
    while( cin>>N[0]>>N[1] )
    {
        ans[0]=ans[1]=INT_MAX;
        for(i=0;i<2;++i)
            for(j=0;j<N[i];++j)
                cin>>d[i][j].first>>d[i][j].second;
        cin>>X>>Y;
        flag = false;
        if( X == Y ) {
            for(i=0;i<100000000;++i);
            for(i=0;i<2;++i)
                for(j=0;j<N[i];++j)
                    if( d[i][j].first <= X && X <= d[i][j].second )
                    {
                        ans[i] = 1 ;
                        break;
                    }
        }
        else
        {
            sort(d[0],d[0]+N[0]);
            sort(d[1],d[1]+N[1]);
            for(i=0;i<2;++i)
            {
                ed = mx = X;
                j = 0;
                while( j!=N[i] && ed < Y )
                {
                    ans[i]++;
                    ed = mx;
                    flag = false;
                    while( j!=N[i] && d[i][j].first <= ed ) {
                        if( d[i][j].second > mx )
                        {
                            flag = true;
                            mx = d[i][j].second;
                        }
                        j++;
                    }
                    if( !flag ) break;
                }
                if( mx < Y ) ans[i] = INT_MAX;
            }
        }
        if( ans[0] == ans[1] && ans[0] == INT_MAX ) cout<<"TIE\n";
        else if( ans[0] <= ans[1] ) cout<<"A WIN\n";
        else cout<<"B WIN\n";
    }
}