减压轻松网站开发,杭州网站建设seo,wordpress手机后台,三门县住房和城乡建设规划局网站P5482 [JLOI2011]不等式组 超烦人的细节题#xff01;(本人调了两天 QAQ ) 这里介绍一种只用到一只树状数组的写法(离线)。 树状数组的下标是#xff1a;所有可能出现的数据进行离散化之后的值。 其含义为#xff1a;当 \(x\) 离散化后值为 \(i\) 时能满足的不等式个数为 \(… P5482 [JLOI2011]不等式组 超烦人的细节题(本人调了两天 QAQ ) 这里介绍一种只用到一只树状数组的写法(离线)。 树状数组的下标是所有可能出现的数据进行离散化之后的值。 其含义为当 \(x\) 离散化后值为 \(i\) 时能满足的不等式个数为 \(query(i)\) 个。 处理数据 首先我们先读入所有数据并对数据处理 \(\text{Add} ~a_i~b_i~c_i\) 若 \(a_i0\) 将 \(a_ixb_ic_i\) 转化成 \(x\ge t_i\) 的形式 。 若 \(a_i0\) 将 \(a_ixb_ic_i\) 转化成 \(x\le t_i\) 的形式 。 并将 \(t_i\) 丢进离散化的序列中。 注意所有的除法运算都是向 \(0\) 取整还要注意除法变号问题等等。 \(\text{Del}\) 在处理 \(\text{Add}\) 时提前记录第 \(x\) 个 \(\text{Add}\) 操作所对应的输入操作编号。 \(\text{Query}\) 将 \(k_i\) 丢进离散化序列中。 之后将序列中的数离散化给 \(\text{Add}\) 中的 \(t_i\) 和 \(\text{Query}\) 中的\(k_i\) 都附上一个离散化后的值( \(Instead_i\) ) 。 计算答案 \(\text{Add}\) 若 \(a_i0\) 则在 \([t_i,\infty)\) 区间内的 \(Instead_x\) 都可以使不等式成立。 同理若 \(a_i0\) 则在 \((-\infty,t_i]\) 区间内的 \(Instead_x\) 都可以使不等式成立。 在区间内加 \(1\) 即可 。 \(\text{Del}\) 和 \(\text{Add}\) 几乎一致变为区间减 \(1\) 。 \(\text{Query}~k_i\) 即可直接查询并输出 \(Query(Instead_i)\) 。 最后附上 100pts 代码 #includebits/stdc.h
using namespace std;
#define Maxn 100005
#define inf 0x7f7f7f7f
typedef long long ll;
inline int rd()
{int x0;char ch,t0;while(!isdigit(ch getchar())) t|ch-;while(isdigit(ch)) xx*10(ch^48),chgetchar();return xt?-x:x;
}
int n,tmp,tot,cnt;
mapint,int mp;
int Ins_val[Maxn],hist[Maxn];
struct Data
{int opt,t,Ins;int pre,used;
}a[Maxn];
int tree[Maxn];
inline int lowbit(int x){ return x(-x); }
void add(int x,int k)
{while(xtot1) tree[x]k,xlowbit(x);
}
int query(int x)
{int ret0;while(x) rettree[x],x-lowbit(x);return ret;
}
int main()
{//freopen(.in,r,stdin);//freopen(.out,w,stdout);nrd();string opt;for(int i1,x,y,z,A,B,C;in;i){cinopt;if(optAdd){Ard(),Brd(),Crd(),hist[cnt]i;a[i].opt2-(A0); // 当 a0 时 opt1 否则 opt2 if(A0) a[i].t(BC)?(-inf1):inf;else if(A0) a[i].t(C-B)/A(((C-B)0)?1:(((C-B)/A*A(C-B))?1:0));else a[i].t(C-B)/A-(((C-B)0)?1:(((C-B)/A*A(C-B))?1:0));Ins_val[tmp]a[i].t;}if(optDel){a[i].prehist[rd()];a[i].opta[a[i].pre].opt2; // 当 a0 时 opt3 否则 opt4 a[i].ta[a[i].pre].t;}if(optQuery) a[i].opt5,a[i].trd(),Ins_val[tmp]a[i].t;}sort(Ins_val1,Ins_val1tmp);Ins_val[0]-inf;for(int i1;itmp;i) if(Ins_val[i]!Ins_val[i-1]) mp[Ins_val[i]]tot;for(int i1;in;i) a[i].Insmp[a[i].t];for(int i1;in;i){if(a[i].tinf) continue; // a0 bcif(a[i].opt1) add(tot1,-1),add(a[i].Ins,1); // a0 || (a0 bc)if(a[i].opt2) add(a[i].Ins1,-1),add(1,1); // a0 if(a[i].opt3 !a[a[i].pre].used) add(tot1,1),add(a[i].Ins,-1),a[a[i].pre].used1; // a0 || (a0 bc)if(a[i].opt4 !a[a[i].pre].used) add(a[i].Ins1,1),add(1,-1),a[a[i].pre].used1; // a0if(a[i].opt5) printf(%d\n,query(a[i].Ins));}//fclose(stdin);//fclose(stdout);return 0;
}
