K

看完题之后思路是很自然的：对于每个要求，就转化成对于l和r的限制。原本被题目解释干扰了，纠结了一下区间长度的限制觉得很复杂；后来发现只要l和r合法，区间长度就合法，所以对于1的限制直接取交，对于2的二选一的限制，直接按照l的限制排序，枚举l所在的区间，即可得到r的范围，再和一开始的交集取交即可。

这思路确实很容易也很好写，但写完疯狂wa2。。。还是有个小细节没注意到，，，有点破防

image
此处要和1取max，因为原本算出来的l可能小于0，原理其实和后面的和L取min是一样的，但1的限制太容易忽略（区间范围关系的计数题，应该把每个限制都写成区间的形式！！而不是只有一边的不等式），，，而且在上面其实考虑过限制1算出来<0的情况，也忘记考虑限制2了，只能说写题的时候脑子比较混乱
image

点击查看代码 
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
const int N=1e5+5,F=2e9+5;
int T,n,m,L,R;
struct node{
	int l,r;
}p[N];
int mn[N];
bool cmp(node u,node v){
	return u.l<v.l;
}
void work(int id){
	cin>>n;
	m=0;
	L=F; R=1;
	while(n--){
		int t;
		ll k,x;
		scanf("%lld%lld%lld",&t,&k,&x);
		ll s=k*(k-1)/2;
		int l=(int)((x-s)/k),r=(int)((x+s-1)/k+1);
		if(t==1) L=min(L,l),R=max(R,r);
		else p[++m]=(node){l,r};
	}
	if(L<=0){
		puts("0");
		return;
	}
	if(L==F){
		puts("-1");
		return;
	}
	sort(p+1,p+m+1,cmp);
	p[0]=(node){0,0};
	p[m+1]=(node){F,F};
	mn[m+1]=F;
	for(int i=m;i;i--) mn[i]=min(p[i].r,mn[i+1]);
	ll ans=0;
	for(int i=0;i<=m;i++){
		int a=max(1ll,p[i].l+1),b=min(L,p[i+1].l);
		if(a>b || mn[i+1]<=R) continue;
		if(b==F || mn[i+1]==F){
			puts("-1");
			return;
		}
		else ans+=1ll*(b-a+1)*(mn[i+1]-R);
	}
	cout<<ans<<endl;
}
signed main()
{
	cin>>T;
	for(int i=1;i<=T;i++) work(i);
	return 0;
}

原文地址：http://www.cnblogs.com/szsz/p/16867303.html

1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！ 2. 分享目的仅供大家学习和交流，请务用于商业用途! 3. 如果你也有好源码或者教程，可以到用户中心发布，分享有积分奖励和额外收入！ 4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！ 5. 如有链接无法下载、失效或广告，请联系管理员处理！ 6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！ 7. 如遇到加密压缩包，默认解压密码为"gltf",如遇到无法解压的请联系管理员！ 8. 因为资源和程序源码均为可复制品，所以不支持任何理由的退款兑现，请斟酌后支付下载 声明：如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性