分类存档：默认分类

【题目大意】

给定ax+by+c=0。求x1<=x<=x2 && y1<=y<=y2的解有多少组。

【算法分析】

见到缺了这种例题，又没A这题，那么就做一下。

例题系列。

首先判断掉a和b中存在0的情况。然后exgcd解出ax+by=gcd(a,b)的一个初始解，

然后假如-c%gcd(a,b)!=0。那么无解。否则a/=g b/=g c/=g。然后x就只能+-b，y对应地+-a。然后用个除法搞一下就可以了。

一开始我后面取范围用倍增算法，就是2进制步长那种跨越的。第3个点居然就TLE了= =。

【时间复杂度】O(lg (x+y))

【空间复杂度】O(1)

【CODE】

#include

这次是我第一次，也是最后一次NOI
由于我是夏令营选手，然后GD夏令营有5个人。每个宿舍能装4个人。5%4==1?
没错，我就是那个1
然后被果断发配到与3个黑龙江夏令营选手一起= =。

7.31
我们很晚才报道。然后与何神（我们尊称为小赖神）等吃了晚饭。。。
然后回到宿舍。发现没有拖鞋洗澡。疼，然后果断去买。
买完回来发现那个厕所激动得停不下来了，一直冲水，疼。。。
然后我们把他活生生拔出来以后才停了。过了一会儿，听过隔壁宿舍的厕所也开始激动了。于是心里平衡一点。。。
然后上上网，就睡了。

8.1
早上开幕式。。。然后各种讲话。让我感觉比较疼的是，映像中各个上去发表讲话的人里，只有1人脱稿。那就是海尔的经理。毕竟还是商人这方便要求比较高啊。。。
然后中午再围观了一下笔试题。下午就去笔试了。
笔试基本是送分。然后这次得了100。
然后那个练习赛的话，前面那题一看到题目搞了n^4的，可以AC了。然后提交答案没搞。。。出来一听，其他人都是O(n)的。。。我真蒟蒻+疼。
然后晚上很早就睡了。不过睡不惯那么硬的枕头。

8.2 Day1
比较紧张。然后看了第一题，哇。。。居然有80分是送人的。高高兴兴搞完，就不理第一题了。
然后看了第二题，感觉有点混乱。
写了个n^3的dp。然后看第3题。
大概思考了20秒。。。很神奇地认为是平面图最小割。但是那个两个不同方向边的不太会搞的样子啊。
然后我记得衡阳八中1001有人用sap依然可以卡过。。。甚至比我的spfa还快。于是我果断写了bfs预处理标号的sap。这样就能保证这题有80分了。
然后回来搞第二题。
第二题我一开始写了n^3的dp。后来用作对拍只用。感觉还是挺好的。
然后我YY了一会儿，想到了二分答案+平衡树的做法。然后就果断敲了。
后来写好以后。。。不会写对拍程序= =。。。我当时就泪奔了。。。
然后回忆笔试内容，知道运行一个文件时./xxxxx 然后我用C++的system("");试了一会儿。
搞的很囧。原因是我是这样写的：system("./makedata.exe");
然后。。。Linux的可执行文件原来是可以没后缀名的。。。
试了一会儿终于可以开始对拍了。
然后平衡树各种写庛= =。
调了N久终于正确了。然后好像我就没做什么了。就是各种对拍与检查文件名等。
然后下午拿到成绩。。。
80+30+90=200。
果断第二题zheyi了。。。70分的算法被我活生生写成30分。。。手测10^5那几个点都是2.xxx s。然后时限是2s。后来叉姐说不用struct封装那个平衡树，可以快3倍= =。。。我当时就囧了。

8.3 社会实践活动
上午去了蓬莱极地世界。。。然后围观各种鱼。然后就走了。囧。
下午去了那个啥沙滩。。。。看着海水泛着绿色的各种草还是啥的。。。果断留在沙滩上。。。
后来WY神牛在那各种打蜻蜓，但是一只都没搞到。表示蜻蜓敏捷太高。。。
后来省队众牛在各种讨论如何制止卢神牛进省队的伟大计划。。。叉姐猜测可能栋栋会因为没见过由卢神牛造成的大场面而泪流满面。。。
然后就回去洗洗睡了。

8.4 Day2
这次一拿到试题。先把所有题都看了一遍。
囧，一题都不会= =。然后貌似记得哪个大牛说要先搞提交答案题。然后我就先搞了。
然后我想了两个贪心的。一个是找距离最近的虾去抓。另一个是找追上时间最短的虾去抓。然后把所有数据都运行了一次，取较优值。
我表示没做过提交答案题。。。不知道要看数据。= =。
然后暴力的第一题和第二题。
然后第二题n=2的情况搞了好久。。。还是没搞出来。主要是顺指针逆时针走的和蛇形走的之间各种嵌套什么的。
然后想给第二题加一个连通性剪枝的。然后后来觉得反正搜索过不了多少，就没加。（事实证明，有30分）
第一题看了一下。决定分段。首先n<=10的30分一定要拿到。然后其他的就乱搞。
我先对那个先后限制当成权为1的有向边。然后Floyed了一下。
然后按照每个点卡的紧要程度拍了下序，然后搜索出一个可行解。那些最前可以是多少就放弃了。
全部输出1。

然后下午看成绩46+30+54=130。感觉第二题的30分比较zheyi。。。其他没什么了。
最后我也不知道什么rank的东西。感觉不知道有没有银牌。
然后后来听到说金牌貌似479，那我就觉得应该有银牌了。

8.5 之后
然后后面的就是各种找学校。
由于我比较囧。。。NOIP没有1=，又是夏令营选手。虽然NOI有430分。但是那个没有1=就没有保送资格。然后只能协商说等拿到一等以后再要。。。

然后现在离NOIP还有两个月。。。这两个月要好好学习文化课。。。毕竟NOIP虽然几乎不可能挂，但是毕竟没拿到保送。。。老师也不会允许我文化课不太努力的= =。。。。
现在。。。回去上文化课。现在就一个字：疼。。。。

【题目大意】给定一个数列。多个询问，问区间中第k小的数是哪个。

【算法分析】

既然是例题系列，那么讲一下划分树。

大体上是采用分治思想。每次取一中位数划分为左右两边。然后在同一区间内，数的顺序与在原数组中的顺序一样。

建立的话。我们可以通过自底向上的归并来达到lg n的建立。

然后询问时，通过To_L[]表示这个区间内，前i个数字有多少个被划分去了左边，可以快速判断。达到lg n的效果。

【其它】

这个英语太强大了。kth big number

【CODE】

#include

#include #include #include #include using namespace std;
const int N=105555;
int Tc,n,m,spt;
int a[N],b[N*20],To_L[N*20];
struct Node{int l,r,St,Ed;}Tr[N*5];
bool cmp(int i,int j){return a[i]     scanf("%d%d",&n,&m);
     for (int i=1;i<=n;i++) scanf("%d",&a[i]);
     for (int i=1;i<=n;i++) b[i]=i;
     sort(b+1,b+n+1,cmp);
     spt=n;
}

void Union(int p,int s1,int e1,int s2,int e2){
     Tr[p].St=spt+1;
     int i=s1,j=s2,Sum=0;
     while (i<=e1 || j<=e2){
       if (i<=e1 && (j>e2 || b[i]                                    else b[++spt]=b[j++];
       To_L[spt]=Sum;
     }
     Tr[p].Ed=spt;
}

void build(int p,int l,int r){
     Tr[p].l=l; Tr[p].r=r;
     if (l==r){
       Tr[p].St=Tr[p].Ed=l;
       return;
     }
     int mid=(l+r)/2,i;
     build(p*2,l,mid);
     build(p*2+1,mid+1,r);
     Union(p,Tr[p*2].St,Tr[p*2].Ed,Tr[p*2+1].St,Tr[p*2+1].Ed);
}

int Query(int p,int l,int r,int k){
    if (Tr[p].l==Tr[p].r) return a[b[Tr[p].St]];
    int LL=0,RR,res;
    RR=To_L[Tr[p].St+r-1];
    if (l!=1) LL=To_L[Tr[p].St+l-2];
    res=RR-LL;
    if (res>=k) return Query(p*2, LL+1 , LL+res ,k);
    else{
      k-=res;
      res=r-l+1-res;
      if (l!=1) LL=l-1-LL;
      return Query(p*2+1,LL+1,LL+res,k);
    }
}

void solve(){
     int l,r,k,i;
     for (i=0;i         scanf("%d%d%d",&l,&r,&k);
         printf("%dn",Query(1,l,r,k));
     }
}

int main(){
    scanf("%d",&Tc);
    for (int i=0;i        init();
        build(1,1,n);
        solve();
    }
    return 0;
}