[BOI2007]Mokia 摩基亚-白红宇

[BOI2007]Mokia 摩基亚

阅读量：5299 次

发布时间：2019-06-14

本文共 1246 字，大约阅读时间需要 4 分钟。

Description:

摩尔瓦多的移动电话公司摩基亚（Mokia）设计出了一种新的用户定位系统。和其他的定位系统一样，它能够迅速回答任何形如“用户C的位置在哪？”的问题，精确到毫米。但其真正高科技之处在于，它能够回答形如“给定区域内有多少名用户？”的问题。

在定位系统中，世界被认为是一个W×W的正方形区域，由1×1的方格组成。每个方格都有一个坐标(x,y)，1<=x,y<=W。坐标的编号从1开始。对于一个4×4的正方形，就有1<=x<=4,1<=y<=4（如图）：

请帮助Mokia公司编写一个程序来计算在某个矩形区域内有多少名用户。

Hint:

\(n \le 2*10^5\)

Solution:

考虑把答案拆成四个矩阵,前缀和运算一下,就是cdq裸题了

#include #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #define ls p<<1 #define rs p<<1|1using namespace std;typedef long long ll;const int mxn=2e6+5;int n,m,cnt,tot,t[mxn],hd[mxn];inline int read() { char c=getchar(); int x=0,f=1; while(c>'9'||c<'0') {if(c=='-') f=-1;c=getchar();} while(c<='9'&&c>='0') {x=(x<<3)+(x<<1)+(c&15);c=getchar();} return x*f;}inline void chkmax(int &x,int y) {if(x
              
               y) x=y;}struct Q { int id,x,y,val,opt;}q[mxn<<2];int cmp(Q x,Q y) { return x.id
               
                >1; cdq(l,mid); cdq(mid+1,r); sort(q+l,q+mid+1,cmp1); sort(q+mid+1,q+r+1,cmp1); int lp=l; for(int i=mid+1;i<=r;++i) { while(q[lp].x<=q[i].x&&lp<=mid) { //这里没取等调了半年 if(!q[lp].opt) mod(q[lp].y,q[lp].val); ++lp; } if(q[i].opt) q[i].val+=query(q[i].y); } for(int i=l;i

转载于:https://www.cnblogs.com/list1/p/10597134.html

你可能感兴趣的文章