题解 P3913 【车的攻击】

stansxt · 2020-04-06 22:04:20 · 题解

前言

蒟蒻第一次交这题果断 TLE，当场懵了：橙题卡常？！复杂度明明 O(n \log_2{n} )的。~~说明窝还是太菜了QwQ~~。然后就不信邪的把lower\_bound换换成手写二分，果然就过了。~~事实证明STL一点都不好使~~ 然后进来扫一圈题解，顿时欲哭无泪：大佬的做法我怎么永远想不到啊/dk。于是乎，就发一篇题解记录一下蒟蒻古怪的想法吧。可能跑得比较慢，但不开O_2也是能过的，最慢的点大概950ms。

大体思路

首先我们考虑N\leqslant10^6的情况。我们考虑每加入一个车后对答案产生的贡献：
- 一个车会影响到一行、一列，那我们先考虑行：
- 若这一行已经被占用过了，那么此车不会再在水平方向做出贡献，跳过。这里就随便开个数组记录下即可。后面代码里的 qa []、qb [] 即是。
- 一行本来会有N个格子，对于之前的每一个已经被计算过的列，都会与该行有一个交点。因此还需要记录一下当前有几个 不同的列被计算过，我用的是nowl、nowr。然后该车在水平方向上的贡献即为N-nowr。
- 竖直方向同理即可。
- 最后注意一下，该点本身并未被覆盖时ans还需要\ +\ +。
然而本题最终数据是N\leqslant10^9，显然数组开不到10^9的，那怎么办呢？
注意看到题中的K\leqslant10^6，那么很容易想到，需要想办法把数组开到K的大小。
考虑把一个车挪动的结果。假设仅挪动这一个车，有了上面的结论，很容易发现只要保证它所在行的是否被攻击的情况不变（就是说如果它本来的位置所在行已经有车，那么它的目标位置所在行也得有车。反之原先行上没有，目标位置所在行也不能有），它对答案的贡献就不变。列同理。
有了这个结论，我们便可以开始挪车了。这个时候很容易想到离散化，只需要找到每个行的排名，把这个行里所有的车移动到它的排名那一行去，这样答案不变。
离散化之后所有的行都在1~10^6中，这样就可以开数组了，相当于N\leqslant10^6的情况。
一定注意不要轻易用lower\_bound，当然用了开O_2也是能过的，但是个人建议手写一个二分查找，反正又不麻烦。我代码里的二分写的很丑，但是保证正确。大家也可以用自己熟悉的写法。注意最好要返回该值第一次出现的位置。
还有就是，程序跑得再慢，ans还是要开long\ long的，这个别忘了。

代码

//P3913 车的攻击        
//submit 3             
//By sxt on 2020.4.6         
#include<bits/stdc++.h>             

#define rg register int                 
#define il inline             
#define in read()                       
#define _num(x) (x >= '0' && x <= '9')   
#define ql(x) memset(x, 0, sizeof(x))   
#define mid ((l + r) >> 1)   
#define el else if     

using namespace std;   

typedef long long ll;   

const int N = 1e6+3;   

il int read(){      
    int x=0,f=1;          
    char ch=getchar();    
    while(!_num(ch)){     
        if(ch=='-')     
            f=-1;      
        ch=getchar();     
    }                
    while(_num(ch)){     
        x=x*10+ch-'0';     
        ch=getchar();     
    }           
    return x*f;               
}                         

char f[20];               
int cnt;                   

il void pint(ll x){              
    if(x == 0){ putchar('0'), putchar('\n'); return ;}            
    cnt = 0;          
    while(x > 0){                   
        f[cnt++] = x % 10 + '0';         
        x /= 10;     
    }     
    while(cnt > 0) putchar(f[--cnt]);   
    putchar('\n');   
    return ;   
}   

int n, m, x, y, a[N], b[N], nowl, nowr, pa[N], pb[N], qa[N], qb[N], k;   
ll ans;     

il int check(int se[], int xx){   
    rg l = 1, r = m;    
    while(l < r - 1){     
        if(xx < se[mid]) r = mid - 1;  
        el(xx > se[mid]) l = mid + 1;  
        else r = mid;    
    }    
    if(se[l] == xx) return l;    
    return r;    
}     

signed main()    
{      
    //freopen("1.txt", "r", stdin);    
    n = in, k = m = in;     
    while(k--){     
        pa[m - k] = a[m - k] = in, pb[m - k] = b[m - k] = in;    
    }     
        //离散化    
    sort(pa + 1, pa + m + 1);     
    sort(pb + 1, pb + m + 1);     
    for(rg i = 1; i <= m; ++ i){    
        a[i] = check(pa, a[i]);   
        b[i] = check(pb, b[i]);   
    }                   
        //离散完成             
        //下面依次加入每一个车        
    for(rg i = 1; i <= m; ++ i){        
        x = a[i], y = b[i];      
        nowl += 1 - qa[x];        
        nowr += 1 - qb[y];      
            //这里注意一下顺序，本行的上下最好不要颠倒，颠倒的话最底下那个if需要做些调整。不懂可以手完一下。         
        if(!qa[x]){     
            ans += n - nowr;     
        }          
        if(!qb[y]){        
            ans += n - nowl;    
        }     
        if(!qb[y] && !qa[x]) ++ ans;   
        qb[y] = 1, qa[x] = 1;    
    }          
    pint(ans);    
    return 0;    
}

最后附个评测记录叭，不开O_2稍显勉强QwQ

THE\ ·\ END.