网站建设 amp 找VX cp5173,舆情监测分析系统,天元建设集团有限公司李家军,怎么简单做网站排名题意#xff1a;有两种操作#xff1a;(1)插入线段#xff0c;第i次插入的线段左边界为Li#xff0c;长度为i (2)删除线段#xff0c;删除第x次插入的线段。每次插入线段之前询问有多少条线段被它覆盖。 思路#xff1a;由于插入的线段长度是递增的#xff0c;所以第i次… 题意有两种操作(1)插入线段第i次插入的线段左边界为Li长度为i (2)删除线段删除第x次插入的线段。每次插入线段之前询问有多少条线段被它覆盖。 思路由于插入的线段长度是递增的所以第i次插入的线段的长度比以前插入的所有线段都要长从以前插入的线段里面任取一条考虑其与当前线段的位置关系主要有以下三种 图中下方表示当前线段。注意到只有被当前线段覆盖的线段它的左右边界和当前线段的左右边界的相对位置是不同的。也就是说查询有多少个线段的右端点小于等于该线段右端点再查询有多少条线段左端点小于该线段的左端点 两者之差就是答案。因为不符合要求的线段同时进入了前者和后者而符合要求的答案只进入了前者。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128 //#pragma comment(linker, /STACK:1024000000)
#include map
#include set
#include cmath
#include ctime
#include deque
#include queue
#include stack
#include vector
#include cstdio
#include string
#include cstdlib
#include cstring
#include iostream
#include algorithmusing namespace std;#define X first
#define Y second
#define pb push_back
#define mp make_pair
#define all(a) (a).begin(), (a).end()
#define fillchar(a, x) memset(a, x, sizeof(a))
#define copy(a, b) memcpy(a, b, sizeof(a))typedef long long ll;
typedef pairint, int pii;
typedef unsigned long long ull;//#ifndef ONLINE_JUDGE
void RI(vectorinta,int n){a.resize(n);for(int i0;in;i)scanf(%d,a[i]);}
void RI(){}void RI(intX){scanf(%d,X);}templatetypename...R
void RI(intf,R...r){RI(f);RI(r...);}void RI(int*p,int*q){int dpq?1:-1;
while(p!q){scanf(%d,p);pd;}}void print(){coutendl;}templatetypename T
void print(const T t){couttendl;}templatetypename F,typename...R
void print(const F f,const R...r){coutf, ;print(r...);}templatetypename T
void print(T*p, T*q){int dpq?1:-1;while(p!q){cout*p, ;pd;}coutendl;}
//#endif
templatetypename Tbool umax(Ta, const Tb){return ba?false:(ab,true);}
templatetypename Tbool umin(Ta, const Tb){return ba?false:(ab,true);}
templatetypename T
void V2A(T a[],const vectorTb){for(int i0;ib.size();i)a[i]b[i];}
templatetypename T
void A2V(vectorTa,const T b[]){for(int i0;ia.size();i)a[i]b[i];}#if 0
const double PI acos(-1.0);
const int INF 1e9 7;
const double EPS 1e-8;
#endif/* -------------------------------------------------------------------------------- */const int maxn 4e5 7;int u[maxn], v[maxn], w[maxn], tot;
pii rem[maxn];class TA {int C[maxn], n;inline int lowbit(int x) { return x -x; }
public:void init(int n) {this-n n;for (int i 1; i n; i ) C[i] 0;}void update(int p, int x) {while (p n) {C[p] x;p lowbit(p);}}int query(int p) {int ans 0;while (p) {ans C[p];p - lowbit(p);}return ans;}
};
TA lta, rta;inline int find(int x) {return lower_bound(w, w tot, x) - w 1;
}int main() {
#ifndef ONLINE_JUDGEfreopen(in.txt, r, stdin);//freopen(out.txt, w, stdout);
#endif // ONLINE_JUDGEint cas 0, n;while (cin n) {tot 0;int len 1;for (int i 0; i n; i ) {scanf(%d%d, u i, v i);if (u[i] 0) {rem[len] mp(v[i], v[i] len);w[tot ] v[i];w[tot ] v[i] len ;}}sort(w, w tot);tot unique(w, w tot) - w;lta.init(tot);rta.init(tot);printf(Case #%d:\n, cas);len 1;for (int i 0; i n; i ) {if(u[i] 1) {pii buf rem[v[i]];int lid find(buf.X), rid find(buf.Y);lta.update(lid, - 1);rta.update(rid, - 1);}else {int lid find(v[i]), rid find(v[i] len );printf(%d\n, rta.query(rid) - lta.query(lid - 1));lta.update(lid, 1);rta.update(rid, 1);}}}return 0;
}转载于:https://www.cnblogs.com/jklongint/p/4723997.html
