ABC106 D - AtCoder Express 2
2019/11/18
数直線上に$ N点があります。
$ M個の区間$ L_i〜$ R_iが与えられます。
クエリが$ Q個与えられます
$ p_i \leq L_j
$ R_j\leq qi
となるような区間$ jがいくつあるか数えてください。
制約
$ 1 \leq N \leq 500
$ 1 \leq M \leq 200000
$ 1 \leq Q \leq 200000
$ 1 \leq L_i\leq R_i \leq N(1\leq i\leq M)
$ 1 \leq p_i\leq q_i \leq N(1\leq i\leq Q)
ポイント
すべてのクエリで区間$ M個すべて計算していては間に合わない
$ Nが小さいので、そこを利用したい
今回は幸い$ Nが小さいので、$ Lと$ Rを二次元で持つことができる
クエリの条件
$ p_i \leq L_j
$ R_j\leq qi
を
$ p_i \leq L_j\leq q_i
$ p_i\leq R_j\leq qi
と読み替えれば、二次元平面の長方形内に含まれる点の数として数えることができる。
長方形内にある個数は、累積和を用いることで高速に計算できる
解説記事
自分なりの解説
類題
code:c++
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i) #define rep1(i,N) for(int i=1;i<int(N);++i) int main() {
cin.tie(0);
ios::sync_with_stdio(false);
cout << fixed << setprecision(20);
int N,M,Q;
cin>>N>>M>>Q;
rep(i,N)rep(j,N){
}
vector<int> L(M),R(M),p(Q),q(Q);
rep(i,M){
}
rep(i, Q){
}
rep1(i,N+1)rep1(j,N+1){
}
rep(i,Q){
int ans = G[qi][qi] - G[pi-1][qi] - G[qi][pi-1] + G[pi-1][pi-1]; cout<<ans<<endl;
}
}
2020/2/2
追記
code:cpp
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i) /*------------------------------------/
for library*/
template<typename T>
class TwoDimCumsum {
public:
int H,W;
vector<vector<T>> d;
TwoDimCumsum(T _H, T _W):H(_H),W(_W),d(_H+1,vector<T>(_W+1,0)){}
void add(int x, int y, int a){
}
void build(){
for(int i = 1; i <= H; ++i){
for(int j = 1; j <= W; ++j){
}
}
}
T query(int sx, int sy, int gx, int gy){
}
//confirm the 2d vector
void debug(){
for(int i = 0;i <= H;++i){
for(int j = 0; j <= W; ++j){
cerr<<dij<<((j == W) ? "\n":" "); }
}
}
};
/*
使い方
1. インスタンス生成 縦横決める
TwoDimCumsum<int> Cumsum(H,W);
2. 座標に埋める
Cumsum.add(x, y, 1)
3. 二次元累積和計算
Cumsum.build()
4. 区間のクエリを受ける
Cumsumq.uery(p, q)
*/
/*------------------------------------*/
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
cout << fixed << setprecision(20);
int N,M,Q;
cin>>N>>M>>Q;
TwoDimCumsum<int> d(N,N);
rep(i,M){
int l,r;
cin>>l>>r;
d.add(l,r,1);
}
d.build();
while(Q--){
int p,q;
cin>>p>>q;
cout<<d.query(p,p,q,q)<<endl;
}
}
2020/2/2
追記
code:cpp
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i) #define rep1(i,N) for(int i=1;i<int(N);++i) #define all(a) (a).begin(),(a).end() typedef long long ll;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
const int INF = 1e9;
const ll INFLL = 1e18;
const ll MOD = 1e9+7;
const double PI = acos(-1.0);
const int dx8 = {1, 0, -1, 0, 1, -1, -1, 1}; const int dy8 = {0, 1, 0, -1, 1, 1, -1, -1}; /*------------------------------------/
for library*/
/*------------------------------------*/
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
cout << fixed << setprecision(20);
vector<vector<int>> vv(505);
int N,M,Q;
cin>>N>>M>>Q;
rep(i,M){
int l,r;
cin>>l>>r;
}
rep(i,505){
}
while(Q--){
int p,q;
cin>>p>>q;
int ans = 0;
for(int i = p;i <=q;i++){
ans += upper_bound(all(vvi), q) - vvi.begin(); }
cout << ans <<endl;
}
}