11月17日——离noip还有2天[绯弹的亚里亚]

啊啊啊啊啊！！！！今天花了两个小时，但是并不知道最后一道题的“扫描线”是个什么东东……最后发现是自己zz，不想打线段树，偷懒打树状数组就GG了。

每日推荐

绯弹的亚里亚也是一部本人很喜爱的……小说。好吧，我真心认为小说比番好看
直接上图，不说废话。今天博主厚道一点，发点p站的图吧

理子赛高！！！！


还是把小说留下吧……
百度云：http://pan.baidu.com/s/1kVBEMwv

正经事！！！！

今天的题总的来说不难，就全发自己的蒟蒻代码吧！

素数密度

大水题！！

题解

……还是给一份吧。

code

#include<set>
#include<list>
#include<deque>
#include<queue>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<string>
#include<vector>
#include<ctime>
#include<stack>
#include<map>
#define clr(x) memset((x),0,sizeof(x))
#define cld(x) memset((x),127/2,sizeof(x))
#define smin(x,y) x=min(x,y)
#define smax(x,y) x=max(x,y)
#define res(i,x,y) for(int i=x;i<=y;i++)
#define rez(i,x,y) for(int i=x;i>=y;i--)
#define INF 2100000000
#define MOD 1000000007
#define ll long long
#define N 1000005
#define P 65536
#define NAME "prime"
using namespace std;
inline void readll(ll &resez){
static char ch;
while((ch=getchar())<'0'||ch>'9');
        resez=ch-48;
while((ch=getchar())>='0'&&ch<='9')
        resez=resez*10+ch-48;
}
bool a[N],mark[N*5];
ll L,R;
int main(){
    freopen(NAME".in","r",stdin);
    freopen(NAME".out","w",stdout);
    readll(L);readll(R);
memset(a,true,sizeof(a));
memset(mark,true,sizeof(mark));
int ans=0;
    a[1]=0;
    res(i,2,sqrt(P))
        res(j,2,P/i)
if (a[i])a[i*j]=0;   
if (R<=P){
        res(i,L,R)
if (a[i]) ans++;
cout<<ans<<endl;
return 0;
    }
    res(i,1,P)
if (a[i])
            res(j,L/i,R/i)mark[i*j-L+1]=0;
    res(i,1,R-L+1)if (mark[i])ans++;
cout<<ans<<endl;
return 0;
}

数页码

还是一道水题……

题解

code

#include<set>
#include<list>
#include<deque>
#include<queue>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<string>
#include<vector>
#include<ctime>
#include<stack>
#include<map>
#define clr(x) memset((x),0,sizeof(x))
#define cld(x) memset((x),127/2,sizeof(x))
#define smin(x,y) x=min(x,y)
#define smax(x,y) x=max(x,y)
#define res(i,x,y) for(int i=x;i<=y;i++)
#define rez(i,x,y) for(int i=x;i>=y;i--)
#define INF 2100000000
#define MOD 1000000007
#define ll long long
#define N 1000005
#define P 65536
#define NAME "count"
using namespace std;
inline void readin(ll &resez){
static char ch;
while((ch=getchar())<'0'||ch>'9');
        resez=ch-48;
while((ch=getchar())>='0'&&ch<='9')
        resez=resez*10+ch-48;
}
ll sum[10],n;
ll ans;
void countnum(){
    res(i,0,9)
        sum[i]=0;
for(ll k=0,s=0,tot=1;n>0;k++,n/=10,tot*=10){
        ll c;
        c=n%10;
        res(i,1,9)        
            sum[i]+=c*k*tot/10;          
        res(i,0,c-1)        
            sum[i]+=tot;           
        sum[c]+=1+s;            
        sum[0]-=tot;
        s+=c*tot;
    }
}
int main(){
    freopen(NAME".in","r",stdin);
    freopen(NAME".out","w",stdout);
    readin(n);
    countnum();
    res(i,1,9)ans+=sum[i]*i;
cout<<ans<<endl;
return 0;   
}

矩形（今天的重头戏）

文件名：brother.pas/c/cpp
时限：1S
空间：256M
Description
胜负胸中料已明，又从堂上出奇兵。秋实大哥是一个下棋好手，独孤求败的他觉得下棋已经无法满足他了，他开始研究一种新的玩法。
在一个n×m的棋盘上，放置了k个车，并且他在棋盘上标出了q个矩形，表示矩形内部是战略要地。
秋实大哥要求一个矩形内的每一个格子，都至少能被一辆在矩形内的车攻击到，那么这个矩形就是被完整保护的。
现在秋实大哥想知道每一个矩形是否被完整保护。
Input
第一行包含四个整数n，m，k，q，表示棋盘的大小，车的数量以及矩形的数量。
接来下k行，每行包含两个整数x，y，表示有一辆车位于从左往右第x列，从下往上第y行。
接下来q行，每行包含四个整数x1，y1，x2，y2，表示一个矩形的左下角和右上角坐标。
1≤n，m≤1e5，1≤k，q≤2e5，1≤x1≤x2≤1e5，1≤y1≤y2≤1e5，1≤x≤1e5，1≤y≤1e5。
Output
输出q行，对于每一次询问，这个矩形若被完整保护了输出”YES”，否则输出”NO”。

Sample input
4 3 3 3
1 1
3 2
2 3
2 3 2 3
2 1 3 3
1 2 2 3
Sample Output
YES
YES
NO
Limit
此题无小数据(这句话吓得我不敢写暴力……)

思考

一开始掉以轻心没看“见在矩形内的车攻击到”，于是乎偷懒写了个树状数组……连样例数据都WA了，于是乎才发现必须用线段树……不会扫描线，但是冥冥中却写了出来（就个sort嘛……），但是线段树来不及调完，就GG了。

题解

矩形：扫描线+线段树
对于一个矩形如果它能被覆盖，则从水平或者竖直方向，必定存在某个方向上每个横线或者竖线上都有车

使用扫描线从左往右扫，我们把每个矩形拆分为入边和出边，对每个矩形加上所有的车按照出边排序(即x坐标排序)

现在我们维护一个线段树，以y坐标为下标，保存这个位置x最大的车的x标，再维护区间最小值

对于每一个车，我们直接在对应位置更新

对于每一个矩形，我们现在是在它的出边位置考虑，那么我们只需要知道出边之内是不是每一个横线上都有一个车

那么查询对应出边的y坐标所夹的那个区间，是否存在一个车，它的最小值比出边的x坐标小

由此即可判断一个矩形有没有被水平方向的车覆盖

同理，我们在竖直方向同样处理一遍，即可知道每个矩形是否被车覆盖

code

#include<set>
#include<list>
#include<deque>
#include<queue>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<string>
#include<vector>
#include<ctime>
#include<stack>
#include<map>
#define Li(x) x<<1
#define Ri(x) x<<1|1
#define clr(x) memset((x),0,sizeof(x))
#define cld(x) memset((x),127/2,sizeof(x))
#define smin(x,y) x=min(x,y)
#define smax(x,y) x=max(x,y)
#define res(i,x,y) for(int i=x;i<=y;i++)
#define rez(i,x,y) for(int i=x;i>=y;i--)
#define INF 2100000000
#define MOD 1000000007
#define ll long long
#define N 200010
#define P 65536
#define NAME "brother"
using namespace std; 
int maxz[N<<2];  
int num[N];
int n,m,k,q;
int ans[N];
char p[2][100]={"NO","YES"};
inline void readin(int &resez){
static char ch;
while((ch=getchar())<'0'||ch>'9');
        resez=ch-48;
while((ch=getchar())>='0'&&ch<='9')
        resez=resez*10+ch-48;
}
struct query{
int lx,rx,ly,ry;
int pos;
bool operator < (const query &b) const{
return rx!=b.rx?(rx<b.rx):(ry<b.ry);
    }
}Q[N];
struct knight{
int x,y;
bool operator < (const knight &b) const {
return x!=b.x?(x<b.x):(y<b.y);
    }
}dot[N];
void swap(int &x,int &y){int c=x;x=y;y=c;}
void up(int rt){maxz[rt]=min(maxz[Li(rt)],maxz[Ri(rt)]);}
void updatapoint(int l,int r,int d,int pos,int rt){  
if(l==r){
        maxz[rt]=d;
return;
    }
int mid=(l+r)>>1;
if(mid>=pos)updatapoint(l,mid,d,pos,Li(rt));  
else updatapoint(mid+1,r,d,pos,Ri(rt));  
    up(rt);
}
int query(int l,int r,int L,int R,int rt){  
if(L<=l&&r<=R)return maxz[rt];
int mid=(l+r)>>1,ret=100000;
if(L<=mid) ret=min(ret,query(l,mid,L,R,Li(rt)));  
if(R>mid) ret=min(ret,query(mid+1,r,L,R,Ri(rt)));  
return ret;
}
void init(){
    readin(n);readin(m);readin(k);readin(q);
    res(i,1,k)
        readin(dot[i].x),readin(dot[i].y);
    res(i,1,q){
        Q[i].pos=i;
        readin(Q[i].lx),readin(Q[i].ly);
        readin(Q[i].rx),readin(Q[i].ry);
    }
}
void work(){
    sort(Q+1,Q+1+q);
    sort(dot+1,dot+1+k);
int r=1;
    res(i,1,q){
while(r<=k&&dot[r].x<=Q[i].rx){
            updatapoint(1,m,dot[r].x,dot[r].y,1);
            ++r;
        }
int dis=query(1,m,Q[i].ly,Q[i].ry,1);
if(dis>=Q[i].lx)ans[Q[i].pos]=1;
    }
}
void sp(){
    swap(n,m);
    res(i,1,k)
        swap(dot[i].x,dot[i].y);
    res(i,1,q){
        swap(Q[i].lx,Q[i].ly);
        swap(Q[i].rx,Q[i].ry);
    }
    clr(maxz);
}
int main(){
    freopen(NAME".in","r",stdin);
    freopen(NAME".out","w",stdout);
    init();
    work();
    sp();
    work();
for(int i=1;i<=q;i++)cout<<p[ans[i]]<<endl;
return 0;
}

说句题外话

一直觉得自己写的线段树很简洁好看……

总结

今天在最后一题上的花费的却是自愿的，毕竟最近很在乎线段树与树状数组这些名字中带“树”的数据结构。
今晚在补补tarjan算法就行了吧……

补图

再发上一张图的时候突然发现了巴哈姆特之怒的图：
于是乎我就颓了一下…………