NC20127. [JLOI2011]不等式组
描述
输入描述
输入第一行为一个正整数 ，代表接下来有N行。
接下来每一行可能有3种形式：
1.“Add a b c”，表明要往不等式组添加一条不等式ax+b > c ；
2.“Del i”，代表删除第i 条添加的不等式（最先添加的是第1条）。
3.“Query k”，代表一个询问，即当x=k 时，在当前不等式组内成立的不等式的数量。
注意一开始不等式组为空，a,b,c,i,k 均为整数，且保证所有操作均合法，不会出现要求删除尚未添加的不等式的情况。
输出描述
对于每一个询问“Query k”，输出一行，为一个整数，代表询问的答案。
示例1
输入:
9 Add 1 1 1 Add -2 4 3 Query 0 Del 1 Query 0 Del 2 Query 0 Add 8 9 100 Query 10
输出:
1 1 0 0
C++14(g++5.4) 解法, 执行用时: 70ms, 内存消耗: 9068K, 提交时间: 2019-09-28 17:53:11
#include <bits/stdc++.h>
using namespace std;
using namespace std;
const int RANGE=1000005;
int n,c[RANGE*2+1005],tot;
pair<int,pair<int,int> > a[100005];
bool vis[100005];
void ins(int x,int y)
{
x+=RANGE+1;x=max(x,1);x=min(x,n);
while (x<=n) c[x]+=y,x+=x&(-x);
}
int query(int x)
{
int ans=0;x+=RANGE+1;x=max(x,1);x=min(x,n);
while (x) ans+=c[x],x-=x&(-x);
return ans;
}
int main()
{
n=RANGE*2+1000;
int T;
scanf("%d",&T);
while (T--)
{
char ch[10];
scanf("%s",ch);
if (ch[0]=='A')
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
tot++;a[tot]=make_pair(x,make_pair(y,z));
if (x==0)
{
if (y>z) ins(-RANGE,1);
continue;
}
if ((z-y)%x==0)
if (x<0) ins(-RANGE,1),ins((z-y)/x,-1);
else ins((z-y)/x+1,1);
else
if (x<0) ins(-RANGE,1),ins((int)floor((double)(z-y)/x)+1,-1);
else ins((int)floor((double)(z-y)/x)+1,1);
}
else if (ch[0]=='D')
{
int w;
scanf("%d",&w);
if (vis[w]) continue;
vis[w]=1;
int x=a[w].first,y=a[w].second.first,z=a[w].second.second;
if (x==0)
{
if (y>z) ins(-RANGE,-1);
continue;
}
if ((z-y)%x==0)
if (x<0) ins(-RANGE,-1),ins((z-y)/x,1);
else ins((z-y)/x+1,-1);
else
if (x<0) ins(-RANGE,-1),ins((int)floor((double)(z-y)/x)+1,1);
else ins((int)floor((double)(z-y)/x)+1,-1);
}
else
{
int w;
scanf("%d",&w);
printf("%d\n",query(w));
}
}
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 153ms, 内存消耗: 8928K, 提交时间: 2019-09-29 10:03:26
#include <bits/stdc++.h>
using namespace std;
const int N = 20000009;
const int F = 1000009;
int n, li;
int c[N];
char s[11];
bool vis[N];
int line[N], ty[N];
void add(int x, int k) {
for (int i = x; i <= 2 * F; i += i & -i) {
c[i] += k;
}
}
int query(int x) {
int re = 0;
for (int i = x; i > 0; i -= i & -i) {
re += c[i];
}
return re;
}
int main () {
scanf("%d", &n);
while (n--) {
int x, y, z;
cin >> s;
if (s[0] == 'A') {
vis[++li] = false;
scanf("%d%d%d", &x, &y, &z);
if (x == 0) {
if (y > z) {
add(1, 1);
line[li] = 1;
} else {
line[li] = 2;
}
ty[li] = -1;
} else {
if (x > 0) {
line[li] = min((int)max(floor((double)(z - y) / x + 1), -F + 1.0), F) + F;
add(line[li], 1);
ty[li] = 1;
} else {
line[li] = min((int)max(ceil((double)(z - y) / x - 1), -F + 1.0), F) + F;
add(1, 1);
add(line[li] + 1, -1);
ty[li] = 0;
}
}
} else if (s[0] == 'D') {
scanf("%d", &x);
if (!vis[x]) {
vis[x] = true;
if (ty[x] == 1) {
add(line[x], -1);
} else if (ty[x] == 0) {
add(1, -1);
add(line[x] + 1, 1);
} else if (ty[x] == -1 && line[x] == 1) {
add(1, -1);
}
}
} else if (s[0] == 'Q') {
scanf("%d", &x);
printf("%d\n", query(x + F));
}
}
return 0;
}