linkkkk
题意：
给出m个操作[ l , r ]，每次将[ l , l + r − 1 ]区间加一问最后有多少个位置为k , 1 < = k < = n k , r < = 2 e 9 , m < = 2 e 5 l
思路1：
一眼差分题，但是有个细节没想好。
将区间提取出来，存一个结构体，p o s表示坐标，o p表示是左端点还是右端点。
按照坐标从小到大排序，维护n o w表示当前点的区间个数。
遍历结构体，每次到达一个新的点，都将该点之前到上一个点的贡献累计，再更新n o w.
细节就是，存的时候区间的右端点要存为l + r l+rl+r，而不是l + r − 1
因为区间差分是要再下一个位置− 1 -1−1的，不如刚开始存的时候就− 1 .思路2对这个的理解可能更明确。
时间复杂度O ( m )
代码1：
// Problem: D - Online games // Contest: AtCoder - AtCoder Beginner Contest 221 // URL: https://atcoder.jp/contests/abc221/tasks/abc221_d // Memory Limit: 1024 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://cpeditor.org) #include<bits/stdc++.h> using namespace std; typedef long long ll;typedef unsigned long long ull; typedef pair<ll,ll>PLL;typedef pair<int,int>PII;typedef pair<double,double>PDD; #define I_int ll inline ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;} #define read read() #define rep(i, a, b) for(int i=(a);i<=(b);++i) #define dep(i, a, b) for(int i=(a);i>=(b);--i) ll ksm(ll a,ll b,ll p){ll res=1;while(b){if(b&1)res=res*a%p;a=a*a%p;b>>=1;}return res;} const int maxn=5e5+7,maxm=1e6+7,mod=1e9+7; ll n,b[maxn]; struct node{ ll pos,op; }a[maxn]; bool cmp(node a,node b){ if(a.pos==b.pos) return a.op>b.op; return a.pos<b.pos; } int main(){ n=read; int idx=0; rep(i,1,n){ ll u=read,v=read; a[++idx]={u,1}; a[++idx]={u+v,-1}; } sort(a+1,a+1+idx,cmp); int now=0,las; for(int i=1;i<=idx;i++){ if(a[i].op==1){ b[now]+=a[i].pos-a[i-1].pos; } else{ b[now]+=a[i].pos-a[i-1].pos; } //cout<<now<<" "<<b[now]<<" "<<a[i].pos<<" "<<a[i].op<<endl; if(a[i].op==1) now++; else now--; } rep(i,1,n) cout<<b[i]<<" "; return 0; }
思路2：
考虑普通差分不可行，看是否能够离散化，以及离散化后对区间的影响。
对于一个区间[ l , l + r − 1 ]，离散化的时候要离散化l , l + r l,
因为后续的差分操作会让下一位− 1，应当是原数组的下一位，而不是离散化后的下一位。
比如原数组为[ 1 , 200 ] , [ 500 , 1000 ]，那么离散化应该是对[ 1 , 201 ] , [ 500 , 1001 ]进行操作，不然再后续的差分就会变成s u m [ 2 + 1 ] − − 而不是s u m [ 201 ] − −
代码2：
// Problem: D - Online games // Contest: AtCoder - AtCoder Beginner Contest 221 // URL: https://atcoder.jp/contests/abc221/tasks/abc221_d // Memory Limit: 1024 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://cpeditor.org) #include<bits/stdc++.h> using namespace std; typedef long long ll;typedef unsigned long long ull; typedef pair<ll,ll>PLL;typedef pair<int,int>PII;typedef pair<double,double>PDD; #define I_int ll inline ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;} #define read read() #define rep(i, a, b) for(int i=(a);i<=(b);++i) #define dep(i, a, b) for(int i=(a);i>=(b);--i) ll ksm(ll a,ll b,ll p){ll res=1;while(b){if(b&1)res=res*a%p;a=a*a%p;b>>=1;}return res;} const int maxn=4e5+7,maxm=1e6+7,mod=1e9+7; ll n,a[maxn],b[maxn],sum[maxn]; vector<ll>nums; map<ll,ll>mp; int main(){ n=read; for(int i=1;i<=n;i++){ a[i]=read,b[i]=read; nums.push_back(a[i]); nums.push_back(a[i]+b[i]); b[i]=a[i]+b[i]; } sort(nums.begin(),nums.end()); nums.erase(unique(nums.begin(),nums.end()),nums.end()); //cout<<nums.size()<<endl; rep(i,1,n){ int posl=lower_bound(nums.begin(),nums.end(),a[i])-nums.begin()+1; int posr=lower_bound(nums.begin(),nums.end(),b[i])-nums.begin()+1; //cout<<posl<<" "<<posr<<endl; sum[posl]++;sum[posr]--; } // for(int i=1;i<=nums.size();i++) sum[i]+=sum[i-1],cout<<sum[i]<<" "; // puts(""); ll las=0; for(int i=1;i<=nums.size();i++){ if(!sum[i]){ sum[i]+=sum[i-1]; } else{ mp[sum[i-1]]+=nums[i-1]-las; sum[i]+=sum[i-1]; las=nums[i-1]; } } for(int i=1;i<=n;i++) cout<<mp[i]<<" "; return 0; }
