DZY 's BLOG

题意：给定n个点，m个询问。每次询问一个矩形内有几个点。坐标范围10^7。

一眼看上去就很水啊。。坐标肯定是要离散化的。。询问跟着一起离散化。。然后以y为第一关键字，x为第二关键字排序。树状数组统计每个点左下角有多少个点。然后加加减减。。

离散化的细节貌似很恶心。。调着调着就A了。。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

char buf[20000000],*pt=buf,*o=buf;

inline int getint(){
    int s=0,f=1; while((*pt!='-')&&(*pt<'0'||*pt>'9'))pt++;
    if(*pt=='-')f=-1,pt++; while(*pt>='0'&&*pt<='9')s=s*10+*pt++-48; return s*f;
}
inline void print(int x){
    char str[30],*p=str; if(!x)*o++=48;
    else{ while(x) *p++=x%10+48,x/=10; while(p--!=str)*o++=*p;}
}

struct point{
    int x,y,id;
    point(){
        id = -1;
    };
    point(int _x,int _y,int _id){
        x = _x, y = _y, id = _id;
    }
}p[2800010];

bool cmp(point a,point b){
    if(a.y == b.y){
        if(a.x == b.x)  return a.id < b.id;
        else    return a.x < b.x;
    }
    return a.y < b.y;
}

int n,m,N,P,pc = 0;
int X[810000],Y[810000],bx[810000],by[810000],bit[2800000],cnt[2800000];

void upd(int x){
    for(;x <= N;x += x & -x)    bit[x] ++;
}
int query(int x){
    int r = 0;
    for(;x;x -= x & -x) r += bit[x];
    return r;
}

int main(){
    fread(buf,1,20000000,stdin);
    n = getint(); m = getint();
    bx[0] = by[0] = 0;
    N = n + 1;
    P = (m << 2) + n;
    bx[N] = by[N] = 12345678;
    
    for(int i = 1;i <= n;i ++){
        X[i] = getint();
        Y[i] = getint();
        bx[i] = ++ X[i];  
        by[i] = ++ Y[i];
    }
    sort(bx + 1, bx + n + 1);
    sort(by + 1, by + n + 1);
    int cx = unique(bx , bx + n + 2) - bx -1;
    int cy = unique(by , by + n + 2) - by -1;
    for(int i = 1;i <= n;i ++){
        p[(m << 2) + i - 1].x = upper_bound(bx,bx + cx,X[i]) - bx;
        p[(m << 2) + i - 1].y = upper_bound(by,by + cy,Y[i]) - by;
    }
    int x1,y1,x2,y2,X1,X2,X3,Y1,Y2,Y3;
    for(int i = 1;i <= m;i ++){
        x1=  getint(); y1=getint();x2=getint();y2=getint();
        X1 = upper_bound(bx,bx + cx,x1) - bx;
        X2 = upper_bound(bx,bx + cx,x2) - bx;
        X3 = upper_bound(bx,bx + cx,x2 + 1) - bx;
        Y1 = upper_bound(by,by + cy,y1) - by;
        Y2 = upper_bound(by,by + cy,y2) - by;
        Y3 = upper_bound(by,by + cy,y2 + 1) - by;
        p[pc] = point(X3,Y3,pc ++);
        p[pc] = point(X1,Y3,pc ++);
        p[pc] = point(X3,Y1,pc ++);
        p[pc] = point(X1,Y1,pc ++);
    }
    
    sort(p,p + P,cmp);
    for(int i = 0;i < P;i ++){
        if(~ p[i].id)   cnt[p[i].id] = query(p[i].x);
        else    upd(p[i].x);
    }
    
    for(int i = 1;i <= m;i ++)
       print(cnt[i - 1 << 2] - cnt[(i - 1 << 2) + 1] - cnt[(i - 1 << 2) + 2] + cnt[(i - 1 << 2) + 3]),*o++='\n';
        
    return fwrite(buf,1,o-buf,stdout),0;
}

关键算法：

Miller-Rabbin判断素数。http://www.dxmtb.com/blog/miller-rabbin/

Pollard-Rho找出整数的任意一个因子。http://www.dxmtb.com/blog/pollard-rho/

先跟着他讲的写了一遍。太神了。

找因子的时候因为找出来的是任意一个。所以还要继续二分直到找到最小的。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int S=30,C=240;
typedef long long ll;
ll An;
ll mul(ll a,ll b,ll c){
    ll r;   for(r=0;b;a=(a<<1)%c,b>>=1) if(b&1) r=(r+a)%c;  return r;
}ll pow(ll a,ll b,ll c){
    ll r;   for(r=1;b;a=mul(a,a,c),b>>=1)   if(b&1) r=mul(r,a,c);    return r;
}int miller_rabbin(ll n){
    if(n==2)    return 1;   if(n<2||!(n&1)) return 0;
    int t=0;    ll a,x,y,u=n-1;
    while(!(u&1))   t++,    u>>=1;
    for(int i=0;i<S;i++){
        a=rand()%(n-1)+1;
        x=pow(a,u,n);
        for(int j=0;j<t;j++){
            y=mul(x,x,n);
            if(y==1&&x!=1&&x!=n-1)  return 0;
            x=y;
        }if(x!=1)   return 0;
    }return 1;
}ll gcd(ll a,ll b){
    return (!b)?a:gcd(b,a%b);
}ll pollard_rho(ll n,ll c){
    ll x,y,d,i=1,k=2;
    x=rand()%(n-1)+1;y=x;
    while(++i){
        x=(mul(x,x,n)+c)%n; 
        d=gcd(y-x,n);
        if(1<d&&d<n)    return d;
        if(x==y)    return n;
        if(i==k)    y=x,k<<=1;
    }
}void find(ll n,ll c){
    ll m;
    if(n==1)    return;
    if(miller_rabbin(n)){ An=min(An,n);   return;}
    m=n;    while(m==n) m=pollard_rho(n,c--);
    find(m,c);  find(n/m,c);
}int main(){
    int tc; scanf("%d",&tc);    ll n;
    while(tc--){
        scanf("%lld",&n);
        if(miller_rabbin(n))    printf("Prime\n");
        else{   An=1ll<<60ll;   find(n,1LL*C);  printf("%lld\n",An);}
    }return 0;
}

求两个串的最长公共子串。串长250000。

很像上一道题处理d[i]数组。

给第一个串建后缀自动机。

第二个串在上面跑即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=510010;
char buf[maxn],*pt=buf;
int l[maxn],fa[maxn],c[maxn][26],rt=1,tot=1,tail=1;
void add(int x){
    int p=tail,np=++tot,r,q;
    l[np]=l[p]+1;   tail=np;
    for(;p&&!c[p][x];p=fa[p])   c[p][x]=np;
    if(!p){ fa[np]=rt;   return;}
    if(l[p]+1==l[q=c[p][x]]){   fa[np]=q;   return;}
    fa[r=++tot]=fa[q];  memcpy(c[r],c[q],sizeof(c[r]));
    l[r]=l[p]+1;    fa[np]=fa[q]=r;
    for(;p&&c[p][x]==q;p=fa[p]) c[p][x]=r;
}int main(){
    fread(buf,1,510000,stdin);  char ch;
    while((ch=*pt++)!='\n') add(ch-'a');
    int p=rt,k=0,x,An=0;    
    while((ch=*pt++)!='\n'){
        if(c[p][x=ch-'a'])    ++k,p=c[p][x],An=max(k,An); else{
            for(;p&&!c[p][x];p=fa[p]);
            if(!p)  p=rt,k=0;   else    k=l[p]+1,p=c[p][x],An=max(k,An);
        }
    }printf("%d\n",An); return 0;
}

二分+后缀自动机还是比较好想的。dp优化只能膜拜题解了。==

题意：给定一些01字符串作为标准作文库。然后给你几篇作文。对于每篇作文，把这篇作文分成若干段后，如果一段的长度不小于L，且是标准作文库中某个字符串的连续子串，这样这一段作文就是匹配的。求L的最大值，使得这篇作文的90%是匹配的。

一眼看出是二分+判定。因为如果L0可行，那小于L0的L都可行。

然后就可以考虑如何判定。分段的话应该是要dp了。设这个作文是S。

先预处理出一个数组d[i],d[i]=max{i-j+1|S[j..i]是标准作文库中某个字符串的连续子串}

这个用后缀自动机。把标准作文库里的所有字符串拼起来。中间加一个分隔符2好了。然后O(n)建后缀自动机。

然后让S在自动机上跑。

跑的过程具体就是：从root开始，如果下一个字符可以转移就转移，更新len值，如果不能就一直回退直到可以转移，回到根了那len=0，如果还没到根，len=当前结点的l值，并且继续转移。

定义数组f[i]为S[1..i]匹配的最大长度。则f[i]=max{f[j]+i-j|i-d[i]<=j<=i-L}。可惜这样dp是O(n^2)的承受不起。

优化：

f[i]=i+max{f[j]-j|i-d[i]<=j<=i-L}。然后令g[j]=f[j]-j。

考虑它的决策区间。

首先i-d[i]是非严格递增的。

如果有某个i，使得i-d[i]>i+1-d[i+1]，由d[i]的意义知S[i-d[i]+1..i]和S[i+1-d[i+1]+1..i+1]是字典中某个串的子串。
由于i-d[i]+1>i+1-d[i+1]+1，知S[i+1-d[i+1]+1..i]也是字典中某个串的子串且比S[i-d[i]+1..i]更长，这与d[i]的定义中的max违背。

i-L是严格递增的。显然。

那么[i-d[i],i-L]只会右移。那么用g[]递减的一个单调队列维护决策区间即可。

最后的复杂度应该是O(nlogn)。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=1100010;
int l[maxn],ch[maxn][3],d[maxn],f[maxn],g[maxn],q[maxn],fa[maxn];
int rt=1,tail=1,tot=1,n,len;    char s[maxn];
void add(int c){
    int p=tail,np=++tot,r,q;
    l[np]=l[p]+1;   tail=np;
    for(;p&&!ch[p][c];p=fa[p])  ch[p][c]=np;
    if(!p){ fa[np]=rt;  return;}
    if(l[p]+1==l[q=ch[p][c]]){  fa[np]=q;   return;}
    fa[r=++tot]=fa[q];  memcpy(ch[r],ch[q],sizeof(ch[r]));
    l[r]=l[p]+1;    fa[np]=fa[q]=r;
    for(;p&&ch[p][c]==q;p=fa[p])    ch[p][c]=r;
}void init(){
    int p=rt,k=0,x;
    for(int i=1;i<=n;i++){
        if(ch[p][x=s[i]-48])    k++,    p=ch[p][x]; else{
            while(p&&!ch[p][x]) p=fa[p];
            if(!p)  p=rt,k=0;   else    k=l[p]+1,p=ch[p][x];
        }d[i]=k;
    }
}int mt(int r){
    int s=1,e=0,t;
    for(int i=1;i<=n;i++){
        if((t=i-r)>=0){
            while(s<=e&&g[q[e]]<g[t])   e--;
            q[++e]=t;
        }while(s<=e&&q[s]<i-d[i])    s++;
        f[i]=f[i-1];
        if(s<=e&&f[i]<g[q[s]]+i)    f[i]=g[q[s]]+i;
        g[i]=f[i]-i;
    }return f[n]>=len;
}int main(){
    int tc,m;   scanf("%d%d",&tc,&m);
    for(int i=1;i<=m;i++){
        scanf("%s",s+1);
        int k=strlen(s+1);
        for(int j=1;j<=k;j++)    add(s[j]-48);
        if(i!=m)add(2);
    }while(tc--){
        scanf("%s",s+1);    n=strlen(s+1);
        len=(int)(ceil((double)n*0.9));
        init(); if(!mt(1)){   printf("0\n");  continue;}
        int L=2,R=n,mid;
        while(L<=R){
            mid=(L+R)>>1;
            if(mt(mid)) L=mid+1;    else    R=mid-1;
        }printf("%d\n",R);
    }return 0;
} 

给定N和G。求Ans=G^(sigma(C(n,i)|i是n的约数))。Ans对999911659取模。

很高兴地发现它是质数。

其实求组合数的话。费马小定理乱搞除法取模。然后用lucas定理。很快就可以求出sigma(C(n,i)|i是n的约数)。

关键是求Ans的时候，这个指数太大了怎么破！

欢迎这个式子登场：a^b mod c=a^(b mod phi(c) + phi(c))。

注意到phi(质数)=质数-1。那么我们要模的就是999911658了。

可是lucas只对质数适用啊。

很高兴的分解质因数，发现999911658=2*3*4679*35617。

那么只需要模这4个数。然后用中国剩余定理合并。

这道题就被水了。一开始95分。发现指数里没有+phi(c)，导致指数是0，挂了一个点。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll mod=999911659ll,mod2=999911658ll;
ll ft[]={2,3,4679,35617},ft2[]={499955829,333303886,213702,28074};
ll p[4],q[4],n,g,m=0;
ll power(ll a,ll b,ll c){
    ll r=1; while(b){ if(b&1) r=r*a%c; b>>=1; a=a*a%c;}
    return r;
}ll calc(ll a,ll b,ll c){
    if(a<b) return 0; if(b>a-b) b=a-b; ll r=1,ca=1,cb=1;
    for(ll i=0;i<b;i++) ca=ca*(a-i)%c,cb=cb*(b-i)%c;
    return ca*power(cb,c-2,c)%c;
}ll lucas(ll a,ll b,ll c){
    ll r=1; while(a&&b&&r) r=r*calc(a%c,b%c,c)%c,a/=c,b/=c;
    return r;
}ll ext_gcd(ll a,ll b,ll&x,ll&y){
    if(!b){ x=1; y=0; return a;}
    ll xx,yy,d=ext_gcd(b,a%b,xx,yy);
    x=yy; y=xx-a/b*yy; return d;
}ll equ(ll a,ll b,ll c){
    ll x,y,d=ext_gcd(a,c,x,y); x*=b/d;
    while(x>=c/d) x-=c/d; while(x<0) x+=c/d;
    return x;
}ll solve(ll a,ll b){
    for(int i=0;i<4;i++) p[i]=lucas(a,b,ft[i]);
    for(int i=0;i<4;i++) q[i]=equ(ft2[i],1,ft[i]);
    ll r=0; for(int i=0;i<4;i++) r=(r+(p[i]*q[i]%mod2)*ft2[i]%mod2)%mod2;
    return r;
}int main(){
    cin>>n>>g;
    for(ll i=1;i*i<=n;i++) if(n%i==0){
        m=(m+solve(n,i))%mod2;
        if(i*i!=n) m=(m+solve(n,n/i))%mod2;
    }cout<<power(g,m+mod2,mod)<<endl;
    return 0;
}

判断连边的时候貌似有点麻烦、注意重合也算挡住。。。

另外如果用费用流替KM的话、不用添加一个点了、因为貌似不用每个点都流、

（其实我是来除草的、、

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;
typedef long long ll;
const int maxm=50000,inf=1061109567;
const ll mod=1000000007;
map<ll,int>id;  char str[30];   ll hash[100];
int h[100],p[maxm],c[maxm],cost[maxm],n1[maxm],q[maxm],sp[100],inq[100];
int D,n,S,T,TT,An=0,path[maxm],w[100][100],pre[100],tot=0,px[100],py[100];
inline void ae(int a,int b,int cc,int co){
    p[tot]=b; c[tot]=cc; cost[tot]=co;  n1[tot]=h[a]; h[a]=tot++;
    p[tot]=a; c[tot]=0;  cost[tot]=-co; n1[tot]=h[b]; h[b]=tot++;
}inline int spfa(){
    memset(sp,63,sizeof(sp));   memset(inq,0,sizeof(inq));
    int head=0,tail=1; sp[S]=0; q[0]=S; inq[S]=1; pre[S]=-1;
    while(head!=tail){
        int u=q[head++]; if(head>=maxm) head-=maxm; inq[u]=0;
        for(int i=h[u];~i;i=n1[i])
            if(c[i]>0&&sp[p[i]]>sp[u]+cost[i]){
                path[p[i]]=i, pre[p[i]]=u, sp[p[i]]=sp[u]+cost[i];
                if(!inq[p[i]]){ inq[p[i]]=1, q[tail++]=p[i]; if(tail>=maxm) tail-=maxm;}
            }
    }return sp[T]!=inf;
}inline int aug(){
    int delta=inf,  flow=0;
    for(int i=T;pre[i]!=-1;i=pre[i]) delta=min(delta,c[path[i]]);
    for(int i=T;pre[i]!=-1;i=pre[i]){
        c[path[i]]-=delta, c[path[i]^1]+=delta;
        flow+=cost[path[i]]*delta;
    }return flow;
}inline int cf(){
    int ret=0; while(spfa()) ret+=aug(); return ret;
}inline ll gethash(char *str){
    ll tmp=0; int len=strlen(str);
    for(int j=0;j<len;j++) if(str[j]>='A' && str[j]<='Z') str[j]=str[j]+32; 
    for(int j=0;j<len;j++){
        tmp=tmp*29+str[j];
        if(tmp>=mod) tmp%=mod;
    }return tmp;
}inline int ok(int u,int v){
    if((px[u]-px[v])*(px[u]-px[v])+(py[u]-py[v])*(py[u]-py[v])>D*D) return 0;
    for(int i=1;i<=n<<1;i++){
        if(i==u||i==v) continue;
        if((px[i]-px[u])*(px[i]-px[v])>0) continue;
        if((py[i]-py[u])*(py[i]-py[v])>0) continue;
        if((px[i]-px[u])*(py[v]-py[i])==(py[i]-py[u])*(px[v]-px[i])) return 0;
    }return 1;
}int main(){
    scanf("%d%d",&D,&n);
    S=0;TT=n<<1|1;T=TT+1;
    memset(h,0xff,sizeof(h));
    for(int i=1;i<=n;i++){
        scanf("%d%d%s",&px[i],&py[i],str);
        px[i]+=50;py[i]+=50;
        id[hash[i]=gethash(str)]=i;
        ae(S,i,1,0);
    }for(int i=1;i<=n;i++){
        scanf("%d%d%s",&px[n+i],&py[n+i],str);
        px[n+i]+=50;py[n+i]+=50;
        id[hash[n+i]=gethash(str)]=n+i;
        ae(n+i,T,1,0);
    }int u,v;
    for(int i=1;i<=n<<1;i++) for(int j=1;j<=n<<1;j++) w[i][j]=1;
    while(1){
        scanf("%s",str);    if(!strcmp("End",str)) break;   u=id[gethash(str)];
        scanf("%s",str);    v=id[gethash(str)];
        scanf("%d",&w[u][v]);   w[v][u]=w[u][v];
    }for(int i=1;i<=n;i++) for(int j=n+1;j<=n<<1;j++) if(ok(i,j)) ae(i,j,1,-w[i][j]);
    printf("%d\n",-cf()); return 0;
}

拿SAM来求字符串的最小表示很煞笔吧、好吧、只是拿来练习SAM用的、

把字符串自复制一遍、然后建SAM、然后从root开始跑，每次都跑最小编号的结点，在上面跑|S|个结点。然后输出当前结点的信息就行了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct SAMNode{
    int ch[26],fa,len;
    inline void init(){
        fa=-1; len=0; memset(ch,0xff,sizeof(ch));
    }
}T[50010];
char s[10010];
int tot,last; 
void add(int c){
    int end=++tot; T[end].init();
    int tmp=last;
    T[end].len=T[last].len+1;
    while(tmp!=-1 && T[tmp].ch[c]==-1){
        T[tmp].ch[c]=end;
        tmp=T[tmp].fa;
    }if(!~tmp) T[end].fa=0;
    else{
        int next=T[tmp].ch[c];
        if(T[tmp].len+1==T[next].len) T[end].fa=next;
        else{
            int np=++tot; T[np].init();
            T[np]=T[next];
            T[np].len=T[tmp].len+1;
            T[end].fa=T[next].fa=np;
            while(tmp!=-1 && T[tmp].ch[c]==next){
                T[tmp].ch[c]=np;
                tmp=T[tmp].fa;
            }
        }
    }last=end;
}int main(){
    int tc;
    scanf("%d",&tc);
    while(tc--){
        tot=0; last=0; T[0].init();
        scanf("%s",s);
        int n=strlen(s);
        for(int i=0;i<n;i++) add(s[i]-'a');
        for(int i=0;i<n;i++) add(s[i]-'a');
        int o=0;
        for(int i=0;i<n;i++) for(int j=0;j<26;j++) if(~T[o].ch[j]){
            o=T[o].ch[j]; break;
        }printf("%d\n",T[o].len-n+1);
    }return 0;
}

理论知识看了好久的说、这里就不写了、

主要的是定义low[u]表示从u或u的子孙出发通过回边可以到达的最低深度优先数dfn[]。

low[u]=min{dfn[u], min{low[w]|w是u的子女}, min{dfn[v]|v与u邻接，且(u,v)是一条回边} }

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
int low[2010],dfn[2010],ss[1010],v[1010],p[2010],n1[2010],h[1010],n,e=0,tot=0;
inline void ae(int a,int b){ p[e]=b; n1[e]=h[a]; h[a]=e++;}
void dfs(int u){
    for(int i=h[u];~i;i=n1[i]) if(!v[p[i]]){
        v[p[i]]=1;
        dfn[p[i]]=low[p[i]]=++tot;
        dfs(p[i]);
        low[u]=min(low[u],low[p[i]]);
        if(low[p[i]]>=dfn[u]) ss[u]++;
    }else low[u]=min(low[u],dfn[p[i]]);
}inline void init(){
    memset(h,-1,sizeof(h));
    memset(v,0,sizeof(v));
    memset(ss,0,sizeof(ss));
    e=0;tot=dfn[1]=low[1]=v[1]=1;
}int main(){
    int u,v,Tc=0;
    while(scanf("%d",&u),u){
        init();
        scanf("%d",&v);
        ae(u,v); ae(v,u);
        n=max(u,v);
        while(scanf("%d",&u),u){
            scanf("%d",&v);
            n=max(n,max(u,v));
            ae(u,v); ae(v,u);
        }dfs(1);
        if(Tc) printf("\n");
        printf("Network #%d\n",++Tc);
        int f=0;
        if(ss[1]>=1) ss[1]--;
        for(int i=1;i<=n;i++) if(ss[i]){
            f=1;
            printf("  SPF node %d leaves %d subnets\n",i,ss[i]+1);
        }if(!f) printf("  No SPF nodes\n");
    }return 0;
}

只是来除个草。。

这和当年CH上某cf赛制的题的B题很像。不过是这个的弱化版。

令f[i]表示第i个上面建仓库，1~i的都处理好了之后的最小花费。

那么f[i]=min{f[j]+w(j,i)}+c[i]

然后把w(j,i)化开：=p[j]*(x[i]-x[j])+p[j+1]*(x[i]-x[j+1])+...+p[i]*(x[i]-x[i])

=x[i]*p[j..i]-p[j]*x[j]+p[j+1]*x[j+1]+...+p[i]*x[i]

很明显前后两项都可以用前缀和数组O(1)出来。sp[i]=p[1..i],spx[i]=p[1]*x[1]+..+p[i]*x[i]

可惜这样还是n^2的。n还是100w这么凶残。

那么考虑斜率优化。

把w(j,i)带进去。

f[i]=min{f[j]+x[i](sp[i]-sp[j])-spx[i]+spx[j]}+c[i];

可以发现决策有单调性，x=sp[i]-sp[j],y=f[j]-spx[i]+spx[j],k=x[i]。那么就行了。O(n)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef double D;
const int maxn=1000005;
const double inf=1e30;
ll x[maxn],p[maxn],c[maxn],sp[maxn],spx[maxn],q[maxn],f[maxn];
inline D slope(int i,int j){
    ll dx=sp[i]-sp[j],dy=f[i]-f[j]+spx[i]-spx[j];
    if(!dx) return (dy>=0)?inf:-inf;
    return (D)dy/(D)dx;
}inline void read(ll &x){
    ll r=0,f=1;char ch;
    for(ch=getchar();(ch!='-')&&(ch<'0'||ch>'9');ch=getchar());
    if(ch=='-') f=-1; else r=ch-'0';
    for(ch=getchar();ch>='0'&&ch<='9';ch=getchar())r=r*10+ch-48;
    x=r*f;
}int main(){
    ll n;read(n);
    for(ll i=1;i<=n;i++){
        read(x[i]);read(p[i]);read(c[i]);
        sp[i]=sp[i-1]+p[i];
        spx[i]=spx[i-1]+p[i]*x[i];
    }ll s=0,e=0;q[0]=0;
    for(ll i=1;i<=n;i++){
        while(s<e&&slope(q[s],q[s+1])<=(D)x[i])s++;
        f[i]=f[q[s]]+x[i]*(sp[i]-sp[q[s]])-(spx[i]-spx[q[s]])+c[i];
        while(s<e&&slope(q[e],q[e-1])>=slope(i,q[e]))e--;
        q[++e]=i;
    }printf("%lld\n",f[n]);
    return 0;
}

分类讨论大丈夫！！！WTF！！！

题意：

1.给你不等式ax>b

2.删除第i条插入的不等式

3.询问x=k时，满足多少个给定的不等式。

n的范围10w，k的绝对值范围是100w。

那么我们可以先解出这个不等式，把符合这个不等式的所有数所在的位置加一。

比如解出来x>1，就把2~100w全都加一。x<1，就把-100w~0全都加一。

那么明显就是修改区间，单点询问。可以用线段树很好的完成。

但是不知道为什么看到100w就后怕写线段树要玩常数。于是选择了树状数组。

用树状数组的话就需要差分。比如[l,r]都加一，那么在l的位置上加一，r+1的位置上减一。这个很基础。

负数的话下标怎么办呢？设置一个偏移量d=100w+1。修改第x个时，在第x+d个位置上修改。保证下标都是正的方便操作。

看来这道题已经没什么问题了。那我们去写写看？好的。

【以下为吐槽，看tips请跳过若干个自然段】

【四天前】树状数组两行秒。ax>b自以为是的除一除就算解好了。样例很快就过了。很自信的交上去。RE还是WA来着。。然后手忙脚乱改一改还是WA。。这个时候想到了对拍。网上搞了个标程拍一拍。。不拍不知道一拍吓一跳。。然后我就被拍扁重建了。（这是替罪羊树？

发现我解ax>b的方法很不科学。感觉都没考虑全。后来直接去玩double。结果精度萎出翔。。

然后我cave in了。。

【今天】上课的时候我重新想了想ax>b该怎么解。考虑a、b的正负，发现四种情况都列出来。四个if即可。最前面再特判一下a=0就没问题了。回来信心满满的写。

造了组大数据对拍过了。很高心。结果还是WA。真是要吐血。后来突然想到，万一它要删除已经删除掉的呢。那我不就挂了吗。于是我再开了个数组记录。这回，过了。。。。。

【吐槽完了】

几个tips：

1.a=0要特判

2.ax>b分四种情况讨论（我是这么做的保险，或者有更神的方法，可惜我不会

3.如果x解出来不在-100w~100w之间要特判

4.删除已经删除的不等式直接continue！！！

贴代码。本人放个r1的代码攒rp好了~

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int d=1000001,n=2000001,r=1000000;
int bit[n+3],A[100005],B[100005],del[100005]={0};
char op,buf[5000000],*p=buf,*o=buf;
inline void upd(int x,int d){ for(;x<=n;x+=x&-x) bit[x]+=d;}
inline int qry(int x){ int s=0; for(;x;x-=x&-x) s+=bit[x]; return s;}
inline int getint(){ int s=0,f=1; while((*p!='-')&&(*p<'0'||*p>'9'))p++;
    if(*p=='-')f=-1,p++; while(*p>='0'&&*p<='9')s=s*10+*p++-48; return s*f;
}inline char getop(){
    while(*p!='Q'&&*p!='A'&&*p!='D')p++; return *p++;
}inline void print(int x){
    char str[30],*pt=str; if(!x)*o++=48;
    else{ while(x) *pt++=x%10+48,x/=10; while(pt--!=str)*o++=*pt;}
}int main(){
    fread(p,1,5000000,stdin);
    int q,a,b,k,i=0,t1,t2,An; q=getint();
    for(int qq=1;qq<=q;qq++){
        op=getop();
        if(op=='A'){
            a=getint(),t1=getint(),t2=getint(); b=t2-t1; ++i; A[i]=a; B[i]=b;
            if(a==0){ if(b<0)upd(1,1);}
            else if(b==0){
                if(a<0) upd(1,1),upd(d,-1); else upd(1+d,1);
            }else if(b>0){
                if(a>0){
                    An=b/a+1;
                    if(-r<=An&&An<=r) upd(An+d,1); else if(An<-r) upd(1,1);
                }else{
                    An=b/(-a)+1;
                    if(-r<=-An&&-An<=r) upd(1,1),upd(-An+d+1,-1);
                    else if(-An>r) upd(1,1);
                }
            }else if(b<0){
                if(a>0){
                    An=(-b-1)/a;
                    if(-r<=-An&&-An<=r) upd(-An+d,1); else if(-An<-r) upd(1,1);
                }else{
                    An=(-b-1)/(-a);
                    if(-r<=An&&An<=r) upd(1,1),upd(An+d+1,-1);
                    else if(An>r) upd(1,1);
                }
            }
        }else if(op=='Q'){
            k=getint();
            print(qry(k+d));*o++='\n';
        }else{
            k=getint();
            if(del[k])continue;
            del[k]=1; a=A[k]; b=B[k];
            if(a==0){ if(b<0)upd(1,-1);}
            else if(b==0){
                if(a<0) upd(1,-1),upd(d,1); else upd(1+d,-1);
            }else if(b>0){
                if(a>0){
                    An=b/a+1;
                    if(-r<=An&&An<=r) upd(An+d,-1); else if(An<-r) upd(1,-1);
                }else{
                    An=b/(-a)+1;
                    if(-r<=-An&&-An<=r) upd(1,-1),upd(-An+d+1,1);
                    else if(-An>r) upd(1,-1);
                }
            }else if(b<0){
                if(a>0){
                    An=(-b-1)/a;
                    if(-r<=-An&&-An<=r) upd(-An+d,-1); 
                    else if(-An<-r) upd(1,-1);
                }else{
                    An=(-b-1)/(-a);
                    if(-r<=An&&An<=r) upd(1,-1),upd(An+d+1,1);
                    else if(An>r) upd(1,-1);
                }
            }
        }
    }return fwrite(buf,1,o-buf,stdout),0;
}

以及这是我贡献的一片红色。