Submission #3000197

---

Source Code Expand

// author: https://arc068.contest.atcoder.jp/users/takeo1116, https://arc068.contest.atcoder.jp/users/kurenaif
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <cassert>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <utility>
#include <tuple>
#include <cctype>
#include <bitset>
#include <complex>
#include <cmath>
#include <array>
using namespace std;
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3fLL
#define MOD 1000000007
#define mp make_pair
#define mt make_tuple
#define pb push_back
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pint;
typedef pair<ll,ll> pll;
typedef tuple<int,int,int> tint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<pint> vpint;
int dx[8]={0,0,-1,1,1,1,-1,-1};
int dy[8]={-1,1,0,0,1,-1,1,-1};
const int SIZE=300050;
//ここまでテンプレ
namespace std {
    template <>
    class hash<std::pair<int, int>> {
    public:
        size_t operator()(const std::pair<int, int>& x) const{
			size_t num = size_t(x.first) * 100000 + x.second;
			return num;
        }
    };
}
vint node;
//↓区間和を求めるSegmentTree
struct SegmentTreeSum {
private:
    int n;
    vector<int> node;

public:
    // 元配列 v をセグメント木で表現する
    SegmentTreeSum(vector<int> v) {
        // 最下段のノード数は元配列のサイズ以上になる最小の 2 冪 -> これを n とおく
        // セグメント木全体で必要なノード数は 2n-1 個である
        int sz = v.size();
        n = 1; while(n < sz) n *= 2;
        node.resize(2*n-1, 0);

        // 最下段に値を入れたあとに、下の段から順番に値を入れる
        // 値を入れるには、自分の子の 2 値を参照すれば良い
        for(int i=0; i<sz; i++) node[i+n-1] = v[i];
        for(int i=n-2; i>=0; i--) node[i] = (node[2*i+1] + node[2*i+2]);
    }
	void update(int x, int val) {
		// 最下段のノードにアクセスする
		x += (n - 1);

		// 最下段のノードを更新したら、あとは親に上って更新していく
		node[x] = val;
		while(x > 0) {
			x = (x - 1) / 2;
			node[x] = (node[2*x+1] + node[2*x+2]);
		}
	}
	int getsum(int a, int b, int k=0, int l=0, int r=-1) {
		// 最初に呼び出されたときの対象区間は [0, n)
		if(r < 0) r = n;

		// 要求区間と対象区間が交わらない -> 適当に返す
		if(r <= a || b <= l) return 0;

		// 要求区間が対象区間を完全に被覆 -> 対象区間を答えの計算に使う
		if(a <= l && r <= b) return node[k];

		// 要求区間が対象区間の一部を被覆 -> 子について探索を行う
		// 左側の子を vl ・ 右側の子を vr としている
		// 新しい対象区間は、現在の対象区間を半分に割ったもの
		int vl = getsum(a, b, 2*k+1, l, (l+r)/2);
		int vr = getsum(a, b, 2*k+2, (l+r)/2, r);
		return (vl + vr);
	}
};
//↑区間和を求めるSegmentTree
int main(){
	int N,M;
	cin>>N>>M;
	//x=l,y=r
	//クエリ<x,0:区間,1:質問,y>
	multiset<tint> Q;
	//クエリに区間を入れる
	for(int i=0;i<N;i++){
		int l,r;
		cin>>l>>r;
		Q.insert(mt(l,0,r));
	}
	//クエリに質問を入れていく
	for(int i=1;i<=M;i++){
		for(int j=i;j<=M;j+=i){
			int a=j-i,b=j;
			//すでに入れてたら入れない
			if(Q.find(mt(b,1,b))==Q.end())
				Q.insert(mt(b,1,b));
			if(Q.find(mt(a,1,b))==Q.end())
				Q.insert(mt(a,1,b));
		}
	}
	//セグ木
	for(int i=0;i<=M+1;i++)
		node.pb(0);
	SegmentTreeSum S(node);
	//クエリを処理する
	unordered_map<pint,int> pam;
	pam.reserve(Q.size());
	for(tint T:Q){
		int a,b,c;
		tie(a,c,b)=T;
		//区間クエリなら、区間を追加する
		if(c==0)
			S.update(b,S.getsum(b,b+1)+1);
		//質問クエリなら、質問に答える
		else{
			pam[mp(a,b)]=S.getsum(b,M+1);
		}
	}

	//答えを求める
	for(int i=1;i<=M;i++){
		int ans=0;
		for(int j=i;j<=M;j+=i){
			int a=j-i,b=j;
			ans+=pam[mp(b,b)]-pam[mp(a,b)];
		}
		cout<<ans<<endl;
	}
	return 0;
}

Submission Info

Judge Result